#include "mountains.h"
#include <vector>
#include <algorithm>
#include <cstdio>
int* base;
int solve(int* begin,int* end){
if(begin==end) return 0;
int ans=1;
std::vector<int*> sub;
for(auto it=begin+1;it!=end;it++){
sub.push_back(it);
}
std::stable_sort(sub.begin(),sub.end(),[begin](int* a,int* b){return (a-begin)*(*b-*begin)>(b-begin)*(*a-*begin);});
std::reverse(sub.begin(),sub.end());
/*
printf("[%ld,%ld):",begin-base,end-base);
for(int* it:sub){
printf("%ld",it-base);
}
printf("\n");
*/
int* last=end;
for(int* it:sub){
if(it>last) continue;
ans+=solve(it+1,last);
last=it;
}
return std::max(ans,solve(begin+1,end));
}
int maximum_deevs(std::vector<int> y) {
base=y.data();
return solve(y.data(),y.data()+y.size());
}
