#include <bits/stdc++.h>

using namespace std;

class ZigZag
{ public:
int longestZigZag(vector <int> sequence)
{
    int n = sequence.size();
    vector <int> pos(n, 1), neg(n, 1);

    for(int i=1; i<n; i++)
    {
        ///Intento alargar la secuencia que termina en i
        for(int j=0; j<i; j++)
        {
            int dif = sequence[i]-sequence[j];
            if(dif < 0)
                neg[i] = max(neg[i], pos[j]+1);
            if(dif > 0)
                pos[i] = max(pos[i], neg[j]+1);
        }
    }

    int res = 0;
    for(int i=0; i<n; i++)
        res = max(res, max(pos[i], neg[i]));
    return res;
}
 };