zigzag

#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>

using namespace std;

ifstream fin("zigzag.in");
ofstream fout("zigzag.out");

int nr[100],sgn[100],lst[100];
vector<int>inp;

int getsgn(int x){
    if(x<0)return -1;
    else return 1;
}

int main()
{
    int n,x;
    fin>>n;
    for(int i=0;i<n;i++){
        fin>>x;
        inp.push_back(x);
    }
    lst[0] = inp[0];
    for(int i=1;i<inp.size();i++){
        for(int j=0;j<i;j++){
            if(sgn[j]==0){
                if(nr[j]+1>nr[i]){
                    nr[i] = nr[j]+1;
                    sgn[i] = getsgn(inp[i]-lst[j]);
                    lst = inp[i];
                }
            }
            else
            if(sgn[j] == -getsgn(inp[i]-lst[j]) && nr[j]+1>nr[i]){
                nr[i] = nr[j]+1;
                sgn[i] = -sgn[j];
                lst = inp[i];
            }

        }
    }


    return 0;
}