#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define lsb(x) (x&(-x))
#define pii pair<int,int>
#define ss second
#define ff first
#define piii pair<int,pii>
#define debu(x) (cerr << #x << " = "<< x << "\n")
#define debu2(x,y) (cerr << #x << " = "<< x << " " << #y << " = " << y << "\n")
#define debu3(x,y,z) (cerr << #x << " = "<< x << " " << #y << " = " << y << " " << #z << " = " << z<< "\n")
#define bitout(x,y) {\
cerr << #x << " : ";\
for (int justforbits = y; justforbits >=0; justforbits--)cout << (((1 << justforbits) & x)>=1);\
cout << "\n";\
}
#define rangeout(j,rangestart,rangeend) {\
cerr << "outputting " << #j<< ":\n";\
for (int forrang = rangestart; forrang <= rangeend; forrang++)cerr << j[forrang] << " ";\
cerr<<"\n";\
}
#define c1 {cerr << "Checkpoint 1! \n\n";cerr.flush();}
#define c2 {cerr << "Checkpoint 2! \n\n";cerr.flush();}
#define c3 {cerr << "Checkpoint 3! \n\n";cerr.flush();}
#define c4 {cerr << "Checkpoint 4! \n\n";cerr.flush();}
#define vi vector<int>
#define vpii vector<pii>
#define fr(i,x,y) for(int i=x;i<=y;i++)
#define defN 200001
vi lvl(defN,-1);
vector<pii>memo(defN);
int t1=0;
pii que(int x)
{
if(lvl[x]!=-1)return memo[x];
auto k=ask(x-1);
memo[x]=mp(k[0],k[1]);
lvl[x]=memo[x].ff+memo[x].ss;
return memo[x];
}
void binsearch(vi& stuffs)
{
if(stuffs.size()==0)return;
int m=stuffs.size()/2;
if(que(stuffs[0]).ss==que(stuffs.back()).ss)return;
vi v1,v2;
int s1=0,e1=m-1,s2=m,e2=stuffs.size()-1;
while(s1<=e1)
{
que(stuffs[s1]);
if(lvl[stuffs[s1]]==t1)break;
s1++;
}
while(s2<=e2)
{
que(stuffs[s2]);
if(lvl[stuffs[s2]]==t1)break;
s2++;
}
while(e1>=s1)
{
que(stuffs[e1]);
if(lvl[stuffs[e1]]==t1)break;
e1--;
}
while(e2>=s2)
{
que(stuffs[e2]);
if(lvl[stuffs[e2]]==t1)break;
e2--;
}
for(int i=s1;i<=e1;i++){v1.pb(stuffs[i]);}
for(int i=s2;i<=e2;i++){v2.pb(stuffs[i]);}
binsearch(v1);binsearch(v2);
}
int find_best(int n)
{
fr(i,1,min(n,480))
{
que(i);
t1=max(t1,lvl[i]);
}
int fir;
fr(i,1,n){if(lvl[i]==t1){fir=i;}}
vi stuffs;
fr(i,fir,n){stuffs.pb(i);}
while(!stuffs.empty())
{
que(stuffs.back());
if(lvl[stuffs.back()]==t1)break;
stuffs.pop_back();
}
binsearch(stuffs);
int ans;
fr(i,1,n){if(lvl[i]==0)ans=i-1;}
return ans;
}
