#include "mountains.h"
#include <vector>
#define x first
#define y second
const int NMAX = 2000;
int N;
int dp[NMAX + 5][NMAX + 5];
int vf;
std::pair <int, int> st[NMAX + 5];
bool ccw(std::pair <int, int> a, std::pair <int, int> b, std::pair <int, int> c) {
return (1LL * a.first * (b.second - c.second) + 1LL * b.first * (c.second - a.second) + 1LL * c.first * (a.second - b.second) <= 0);
}
void Push(std::pair <int, int> dot) {
while(vf > 1 && ccw(st[vf], st[vf - 1], dot))
vf--;
st[++vf] = dot;
}
int maximum_deevs(std::vector<int> y) {
N = (int)y.size();
for(int i = N; i >= 1; i--) {
vf = 0;
for(int j = i; j <= N; j++) {
Push({j, y[j - 1]});
dp[i][j] = 1;
if(vf >= 1) {
int t = st[vf].first;
dp[i][j] = std::max(dp[i][j], dp[i][t - 1] + dp[t + 1][j]);
}
if(vf > 1) {
int s = st[vf - 1].first;
dp[i][j] = std::max(dp[i][j], dp[i][s - 1] + dp[s + 1][j]);
}
}
}
return dp[1][N];
}
