#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(time(0));
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];
}
void solve(int l, int r)
{
if (l>r||s) return;
if (l==r) return ask2(l), void();
int md=(l+r)/2;
if (ask2(md)[0]-ask2(l-1)[0]>0) solve(l, md-1);
if (ask2(md)[1]-ask2(r+1)[1]>0) solve(md+1, r);
}
int find_best(int n) {
mx=n;
for (int i=0; i<=100; i++) rd=(rng()%n+n)%n, w=max(w, ask2(rd)[0]+ask2(rd)[1]);
solve(0, n-1);
return ans;
}
