#include "mountains.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
#ifdef LOCAL
#define err cout
#else
#define err if (0) cout
#endif
vector<vector<int>> make_graph (vector<int> y){
int n = y.size();
vector<vector<int>> ret(n);
for (int i = 0; i < n; i++){
vector<int> vt(n-i-1);
iota(vt.begin(), vt.end(), i+1);
sort(vt.begin(), vt.end(), [&](int a, int b){
if ((y[a]-y[i])*(b-i) == (y[b]-y[i])*(a-i))
return a > b;
return (y[a]-y[i])*(b-i) > (y[b]-y[i])*(a-i);
});
int mn = INT_MAX;
for (int j : vt){
if (mn > j){
ret[i].push_back(j);
ret[j].push_back(i);
}
mn = min(mn, j);
}
}
return ret;
}
signed maximum_deevs(std::vector<signed> y){
vector<int> z;
for (int i : y)
z.push_back(i);
auto adj = make_graph(z);
int n = y.size();
vector<int> cnt(n);
vector<bool> been(n, 0), bad(n, 0);
for (int i = 0; i < n; i++)
cnt[i] = adj[i].size();
for (int k = n; k--;){
pair<int, int> best = {INT_MAX, -1};
for (int i = 0; i < n; i++)
if (!been[i] && !bad[i])
best = min(best, {cnt[i], i});
if (!~best.s)
break;
been[best.s] = true;
for (int i : adj[best.s]){
if (bad[i])
continue;
if (been[i])
continue;
bad[i] = true;
for (int j : adj[i])
cnt[j]--;
}
}
return count(bad.begin(), bad.end(), 0);
}
#undef int
#undef f
#undef s
#undef err
