#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <climits>
#include <cassert>
#include <tuple>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
using namespace std;
typedef long long LL;
typedef vector<int> Vi;
typedef vector<LL> VL;
typedef vector<bool> Vb;
typedef vector<vector<int>> Vii;
#define forR(i, n) for (int i = 0; i < (n); i++)
template <typename T>
vector<size_t> sort_indexes(vector<T> v) {
vector<size_t> idx(v.size());
iota(idx.begin(), idx.end(), 0);
stable_sort(idx.begin(), idx.end(),
[&v](size_t i1, size_t i2) {return v[i1] < v[i2]; });
return idx;
}
int see[2003][2003];
int dp[2003][2003];
struct Frac { // a / b
int a, b;
};
bool ge(Frac x, Frac y) {
return (LL)x.a * y.b >= (LL)y.a * x.b;
}
int maximum_deevs(Vi y) {
int n = y.size();
memset(see, 0, sizeof(see));
Vi cnt(n);
forR(i, n) {
Frac view{ INT_MIN, 1 };
for (int j = i - 1; j >= 0; j--) {
Frac vj{ y[j] - y[i], i - j };
if (ge(vj, view)) {
view = vj;
see[i][j] = 1;
cnt[i]++;
}
}
view = { INT_MIN, 1 };
for (int j = i + 1; j < n; j++) {
Frac vj{ y[j] - y[i], j - i };
if (ge(vj, view)) {
view = vj;
see[i][j] = 1;
cnt[i]++;
}
}
}
memset(dp, 0, sizeof(dp));
// dp[i][j] [i, j)
forR(i, n) dp[i][i] = 0;
for (int j = 1; j <= n; j++) {
dp[j - 1][j] = 1;
// choose (j-1)
int last = j - 1;
int sum = 1;
for (int k = j - 2; k >= 0; k--) {
if (see[j - 1][k]) {
sum += dp[k + 1][last];
last = k;
}
dp[k][j] = max(dp[k][j - 1], dp[k][last] + sum);
}
}
return dp[0][n];
}
#ifdef TEST_LOCAL
int main() {
auto r = maximum_deevs(Vi{ 0,1,1000000,1500001,1499997,1499992,1499986,1499979,1499971,1499962,1499952,1499941,1499929,1499916,1499902,1499887,1499871,1499854,1000000000 });
return 0;
}
#endif
