#include <bits/stdc++.h>
#include "mountains.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2018;
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))
int N;
int dp[MAXN][MAXN], A[MAXN];
int maximum_deevs (vector<int> v) {
N = v.size();
copy(all(v), A);
for (int rt = 0; rt < N; rt++) {
dp[rt][rt] = 1;
int block = rt; //which one IS BLOCKING others?
int notsee = 0; //which one you guarantee not see?
for (int lt = rt - 1; lt >= 0; lt--) {
dp[lt][rt] = dp[lt][rt - 1];
ll dx1 = block - lt, dy1 = A[block] - A[lt], dx2 = rt - lt, dy2 = A[rt] - A[lt];
if (dx1 * dy2 >= dx2 * dy1) {
if (lt + 1 <= block - 1) {
notsee += dp[lt + 1][block - 1];
}
block = lt;
}
dp[lt][rt] = max(dp[lt][rt], notsee + 1 + (lt < block ? dp[lt][block - 1] : 0));
}
}
return dp[0][N - 1];
}
