#include "mountains.h"
#include <bits/stdc++.h>
#include <cstdio>
#include <vector>
#include <cassert>
typedef long long ll;
const int MAX_N = 2048;
const int INF = 1e9;
ll dp[MAX_N][MAX_N];
struct Point{
int x, y;
};
ll signedArea( Point& a, Point& b ){
return (ll)( a.x * b.y ) - ( a.y * b.x );
}
ll signedArea( Point& a, Point& b, Point& c ){
Point v1 = {b.x - a.x, b.y - a.y};
Point v2 = {c.x - a.x, c.y - a.y};
return signedArea( v1, v2 );
}
bool cw( Point& a, Point& b, Point& c ){
return ( signedArea( a, b, c ) <= 0ll );
}
Point p[MAX_N];
int maximum_deevs(std::vector<int> a){
int n = a.size();
/*
std::reverse(a.begin(), a.end());
a.push_back(INF);
std::reverse( a.begin(), a.end() );
n++;
*/
for( int i=0 ; i<n ; i++ ){
p[i] = {i, a[i]};
}
for( int i=0 ; i<n ; i++ ){
dp[i][i] = 1ll;
// if( i ) dp[i-1][i] = 1;
ll sum = 0;
int last = i;
// std::cerr<<i<<":\n";
for( int j=i-1; j>=0 ; j-- ){
std::cerr<<" - "<<j<<"\n";
dp[j][i] = dp[j][i-1];
if( cw( p[i], p[last], p[j] ) ){
// std::cerr<<" new last \n";
sum += dp[j+1][last-1];
// std::cerr<<" + "<<dp[j+1][last-1]<<"\n";
last = j;
}
dp[j][i] = std::max( dp[j][i], sum + 1 + dp[j][last-1] );
// std::cerr<<" dp["<<j<<"]["<<i<<"] = "<<dp[j][i]<<"\n";
}
}
return dp[0][n-1];
}
