#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
const int nx=2e5+5;
int w, N, ans, mx,cnt, rd;
bool s;
vector<int> m[nx];
vector<int> ask2(int x)
{
if (x<0||x>=mx) return vector<int> (2, 0);
if (m[x].empty())
{
m[x]=ask(x);
if (m[x][0]+m[x][1]==0) ans=x, s=1;
return m[x];
}
return m[x];
}
void solve(int l, int r)
{
if (l>r||s) return;
if (l==r) return ask2(l), void();
int ml=(l+r)/2, mr=(l+r)/2;
while (ml>=l&&ask2(ml)[0]+ask2(ml)[1]!=w) ml--;
while (mr<=r&&ask2(mr)[0]+ask2(mr)[1]!=w) mr++;
if (ask2(ml)[0]-ask2(l-1)[0]>0) solve(l, ml-1);
if (ask2(mr)[1]-ask2(r+1)[1]>0) solve(mr+1, r);
}
int find_best(int n) {
mx=n;
for (int i=0; i<=500; i++) rd=i, w=max(w, ask2(rd)[0]+ask2(rd)[1]);
int l=0, r=n-1;
while (ask2(l)[0]+ask2(l)[1]!=w) l++;
while (ask2(r)[0]+ask2(r)[1]!=w) r--;
solve(l+1, r-1);
return ans;
}
