#include "mountains.h"
#include <bits/stdc++.h>
#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()
#define ll long long
using namespace std ;
struct Fraq
{
ll num , den ;
Fraq(ll num = 0 , ll den = 1 ) : num(num), den(den) {}
bool operator < (Fraq other) const { return num * other.den < den * other.num ; }
bool operator == (Fraq other) const { return num * other.den == den * other.num ; }
bool operator > (Fraq other) const { return num * other.den > den * other.num ; }
} ;
int maximum_deevs(std::vector<int> y) {
int n = sz(y) ;
vector<int> dp(n,1) ;
for(int i = n-1 ; i >= 0 ; i-- )
{
set<Fraq> s ;
for(int j = i + 1 ; j < n ; j++ )
{
Fraq slope = Fraq( y[j] - y[i] , j - i ) ;
if(s.upper_bound(slope) != s.end() ) dp[i] = max(dp[i] , dp[j] + 1 ) ;
s.insert(Fraq(y[j], j) ) ;
}
}
return *max_element(all(dp) ) ;
}
