#include "mountains.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int maximum_deevs(vector<int> y) {
int n = y.size();
vector<int> v(1);
for (int i = 0; i < n; i++) v.push_back(y[i]);
// dp[l][r] stores the maximum number of demons you can place between points l and r
vector<vector<int>> dp(n+1, vector<int>(n+1));
for (int r = 1; r <= n; r++) {
dp[r][r] = dp[r-1][r] = 1;
int last = r-1; // index of last point visible from rth point
int sum = 0;
for (int l = r-2; l > 0; l--) {
if (1ll*(v[r]-v[last])*(r-l) >= 1ll*(v[r]-v[l])*(r-last)) {
sum += dp[l+1][last-1];
last = l;
}
dp[l][r] = max(dp[l][r-1], dp[l][last-1]+sum+1);
}
}
return dp[1][n];
}
