#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
// A Point struct makes the geometry logic much easier to read
struct Point {
long long x, y;
};
// This function checks if the line between Point A and Point C
// is "blocked" by Point B.
// Mathematically, it checks if the slope of AB is >= the slope of AC.
bool is_visible(Point a, Point b, Point c) {
// Cross product to avoid floating point division (slope comparison)
// (b.y - a.y) / (b.x - a.x) >= (c.y - a.y) / (c.x - a.x)
return (b.y - a.y) * (c.x - a.x) >= (c.y - a.y) * (b.x - a.x);
}
int maximum_deevs(vector<int> h) {
int n = h.size();
if (n == 0) return 0;
vector<Point> pts(n);
for (int i = 0; i < n; i++) {
pts[i] = {(long long)i, (long long)h[i]};
}
// dp[i][j] = max deevs we can place in the range of mountains from index i to j
vector<vector<int>> dp(n, vector<int>(n, 0));
// We process ranges by their end point 'right'
for (int right = 0; right < n; right++) {
// Base case: a single mountain can always hold 1 deev
dp[right][right] = 1;
int last_seen = -1;
int hidden_valleys_sum = 0;
// Look at all possible starting points 'left' for a range ending at 'right'
for (int left = right - 1; left >= 0; left--) {
// 1. Calculate the case where we DON'T pick the 'right' mountain
int opt_exclude = dp[left][right - 1];
// 2. Calculate the case where we DO pick the 'right' mountain
// If it's the first mountain to the left, or it's visible over the last mountain we saw
if (last_seen == -1 || is_visible(pts[right], pts[last_seen], pts[left])) {
// If there was a gap between the current mountain and the last visible one,
// those mountains are "hidden" and can be solved as a sub-problem.
if (last_seen != -1) {
hidden_valleys_sum += dp[left + 1][last_seen - 1];
}
last_seen = left;
}
// We pick mountain 'right' (1), add the sum of all hidden valleys found so far,
// and add the remaining mountains to the left of our current view.
int opt_include = 1 + hidden_valleys_sum + (left < last_seen ? dp[left][last_seen - 1] : 0);
dp[left][right] = max(opt_exclude, opt_include);
}
}
return dp[0][n - 1];
}
