#include "mountains.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int D[2005][2005];
// if j > i D[j][i] == 0
bool able(int i, int j, int k, vector<int> &y){
ll ax = i, bx = j, cx = k;
ll ay = y[i], by = y[j], cy = y[k];
ll ret = ax*by + bx*cy + cx*ay;
ret -= bx*ay + cx*by + ax*cy;
return ret >= 0;
}
int maximum_deevs(vector<int> y){
int n = (int) y.size();
y.insert(y.begin(), 0);
for (int i=1; i<=n; i++){
//i is the last deev
D[i][i] = D[i-1][i] = 1;
int l = i-1;
int inside = 0;
for (int j=i-2; j>=1; j--){
if (able(j, l, i, y)){ // j is visible
inside += D[j+1][l-1];
l = j;
}
D[j][i] = max(D[j][i-1], D[j][l-1]+inside+1);
}
}
return D[1][n];
}
