#include"mountains.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#define pb push_back
#define mp make_pair
#define taskname "A"
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const int maxn = 2e3 + 5;
const int mod = 1e9 + 7;
int n;
vector<int> a;
int f[maxn][maxn];
int solve(int l , int r){
if(l == r)return 1;
if(l > r)return 0;
int & res = f[l][r];
if(res > 0)return res;
int mx = l;
for(int i = l ; i <= r ; ++i)if(a[mx] < a[i])mx = i;
int sum = 1;//choose mx
auto See = [&](int i , int j , int k)->bool{
return 1ll * (a[i] - a[j]) * (i - k) > 1ll * (a[i] - a[k]) * (i - j);
};
for(int i = mx + 1 ; i <= r ; ){
int j = i + 1;
for( ; j <= r ; ++j){
if(See(mx,i,j)){
if(j == r)sum += solve(i + 1, r);
}else{
sum += solve(i + 1 , j - 1);
break;
}
}
i = j;
}
for(int i = mx - 1 ; i >= l ; ){
int j = i - 1;
for( ; j >= l ; --j){
if(See(j,i,mx)){
if(j == l)sum += solve(l , i - 1);
}else{
sum += solve(j + 1 , i - 1);
break;
}
}
i = j;
}
return res = max(sum , solve(l , mx - 1) + solve(mx + 1 , r));
}
int maximum_deevs(vector<int> A) {
a = A;
n = a.size();
return solve(0 , n - 1);
}
//int main()
//{
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// if(fopen(taskname".INP","r")){
// freopen(taskname".INP", "r",stdin);
// freopen(taskname".OUT", "w",stdout);
// }
//
//}
