#include "mountains.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int MAXN = 2010;
struct point
{
lli x, y;
point(lli x = 0, lli y = 0)
: x(x), y(y) {}
lli operator * (point a) { return x*a.y - y*a.x; }
point operator - (point a) { return point( x - a.x , y - a.y ); }
};
int n;
int v[MAXN];
int dp[MAXN][MAXN];
int maximum_deevs(vector<int> y)
{
n = (int)y.size();
for(int i = 1 ; i <= n ; i++)
v[i] = y[i - 1];
for(int L = n ; L > 0 ; L--)
{
dp[L][L] = 1;
int sum = 0;
int last = L + 1;
vector<point> cHull( 1 , point( L , v[L] ) );
for(int R = L + 1 ; R <= n ; R++)
{
point cur( R , v[R] );
dp[L][R] = dp[L + 1][R];
while( (int)cHull.size() > 1 )
{
point A = cHull[ (int)cHull.size() - 1 ];
point origin = cHull[ (int)cHull.size() - 2 ];
if( (cur - origin)*(A - origin) > 0 ) break;
cHull.pop_back();
}
if( (int)cHull.size() == 1 )
{
sum += dp[last][R - 1];
last = R + 1;
}
cHull.push_back( cur );
dp[L][R] = max( dp[L][R] , sum + 1 + dp[last][R] );
}
}
return dp[1][n];
}
