#include<bits/stdc++.h>
#include "mountains.h"
#define ll long long int
#define pb push_back
#define mp make_pair
#define FOR(i,n) for(i=0;i<(n);++i)
#define FORe(i,n) for(i=1;i<=(n);++i)
#define FORr(i,a,b) for(i=(a);i<(b);++i)
#define FORrev(i,n) for(i=(n);i>=0;--i)
#define F0R(i,n) for(int i=0;i<(n);++i)
#define F0Re(i,n) for(int i=1;i<=(n);++i)
#define F0Rr(i,a,b) for(ll i=(a);i<(b);++i)
#define F0Rrev(i,n) for(int i=(n);i>=0;--i)
#define ii pair<ll,ll>
#define vi vector<ll>
#define vii vector<ii>
#define ff first
#define ss second
#define cd complex<double>
#define vcd vector<cd>
#define ldd long double
#define dbgLine cout<<"Line : "<<__LINE__<<'\n'
#define all(x) (x).begin(),(x).end()
using namespace std;
/*
const short int __PRECISION = 10;
const ll MOD = 1e9+7;
const ll INF = 1e17 + 1101;
const ll LOGN = 17;
const ll MAXN = 2e5+5;
const ll ROOTN = 320;
const ldd PI = acos(-1);
const ldd EPS = 1e-7;
*/
#define INF 100000000000000000
inline bool xr(bool a, bool b)
{
return ((a && (!b)) || (b && (!a)));
}
ii mx(ii slope1, ii slope2)
{
return ((xr( slope1.ff * slope2.ss > slope2.ff * slope1.ss , slope1.ss * slope2.ss < 0)) ? slope1 : slope2);
}
/*
int maximum_deevs(vector<int> y)
{
int N = y.size();
pair<int, int> A[N];
ii maxSlope[N][N];
F0R(i, N)
F0R(j, N)
maxSlope[i][j] = mp(-INF,1);
F0R(i, N)
F0Rr(j, i+1, N)
{
maxSlope[i][j] = mx(maxSlope[i][j-1], mp(y[j] - y[i], j - i));
// cout<<"maxSlope["<<i<<"]["<<j<<"] = "<<maxSlope[i][j].ff<<'/'<<maxSlope[i][j].ss<<'\n';
}
F0R(i, N)
A[i] = mp(y[i], i);
sort(A, A + N);
vector<int> Answer;
F0R(i, N)
{
bool ok = true;
// cout<<A[i].ff<<","<<A[i].ss<<'\n';
for(int j : Answer)
{
int a = min(A[i].ss, j), b = max(A[i].ss, j);
if(mx(maxSlope[a][b],mp((ll)y[b] - y[a], (ll)b - a)) == mp((ll)y[b] - y[a], (ll)b - a))
{
ok = false;
break;
}
}
if(ok)
Answer.pb(A[i].ss);
// else
// cout<<"no\n";
}
// cout<<Answer.size()<<'\n';
// for(int i : Answer)
// cout<<y[i]<<' '<<i<<'\n';
return Answer.size();
}*/
int maximum_deevs(vector<int> y)
{
int N = y.size();
// pair<int, int> A[N];
ii maxSlope[N][N];
F0R(i, N)
F0R(j, N)
maxSlope[i][j] = mp(-INF,1);
F0R(i, N)
F0Rr(j, i+1, N)
{
maxSlope[i][j] = mx(maxSlope[i][j-1], mp(y[j] - y[i], j - i));
// cout<<"maxSlope["<<i<<"]["<<j<<"] = "<<maxSlope[i][j].ff<<'/'<<maxSlope[i][j].ss<<'\n';
}
pair<int, int> ans = mp(-1, -1);
F0R(mask, (1<<N))
{
vector<int> tmp;
bool ok = true;
F0R(i, N)
if(mask&(1<<i))
tmp.pb(i);
for(int i : tmp)
{
for(int j : tmp)
{
if(i == j)
continue;
int a = min(i, j), b = max(i, j);
if(mx(maxSlope[a][b],mp((ll)y[b] - y[a], (ll)b - a)) == mp((ll)y[b] - y[a], (ll)b - a))
{
// cout<<(bitset<6>(mask).to_string())<<" not ok due to indices "<<a<<" and "<<b<<'\n';
ok = false;
break;
}
}
if(!ok)
break;
}
if(ok)
ans = max(ans, mp(__builtin_popcount(mask), mask));
}
// cout<<"found "<<(bitset<6>(ans.ss).to_string())<<'\n';
return ans.ff;
}
/*
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N;
vector<int> y;
cin>>N;
F0R(i, N)
{
int j;
cin>>j;
y.pb(j);
}
cout<<maximum_deevs(y)<<' '<<maximum_deevs_brute(y);
int a = 0, b = 0;
int r = 3, cnt=0;
while(a == b)
{
N = rand()%r;
if(N == 0) N = r;
y.clear();
y.resize(N);
for(int& x : y)
x = rand()%100000;
a = maximum_deevs(y);
b = maximum_deevs_brute(y);
cout<<++cnt<<'\n';
}
cout<<"Input : "<<N<<'\n';
for(int x : y)
cout<<x<<' ';
cout<<'\n'<<a<<' '<<b;
return 0;
}
5
26924 19072 6270 5829 26777
1 2
4
5686 6021 11662 14721
1 2
*/
