#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
const int maxn=2e5+5;
vector<int>pos,f;
int N,mx=0,q=0;
int L[maxn],R[maxn];
void solve(int l,int r,bool have){
if(r<l) return;
if(have==false){
vector<int>res=ask(r);
L[r]=res[0];
R[r]=res[1];
if(res[0]+res[1]==mx&&L[pos.back()]==L[r]){
for(int i=l;i<=r;i++){
L[i]=L[r];
R[i]=R[r];
pos.pb(i);
}
return;
}
}
int mid=(l+r)/2;
vector<int>res=ask(mid);
L[mid]=res[0];
R[mid]=res[1];
if(res[0]+res[1]==mx){//u
if(L[pos.back()]==L[mid]){//nothing is between them
for(int i=l;i<=mid;i++){
L[i]=L[mid];
R[i]=R[mid];
pos.pb(i);
}
solve(mid+1,r,false);
return;
}
solve(l,mid-1,true);
pos.pb(mid);
solve(mid+1,r,true);
}
else{
solve(l,mid-1,true);
f.pb(mid);
solve(mid+1,r,true);
}
return;
}
int find_best(int n){
N=n;
for(int i=0;i<min(447,n);i++){
vector<int>res=ask(i);
L[i]=res[0];
R[i]=res[1];
if(res[0]+res[1]==0){
return i;
}
mx=max(mx,res[0]+res[1]);
}
for(int i=0;i<min(447,n);i++){
if(L[i]+R[i]==mx){
pos.pb(i);
}
else{
f.pb(i);
}
}
if(R[pos.back()]>0){
solve(pos.back()+1,n-1,true);
}
for(int i:f){
if(L[i]+R[i]==0){
return i;
}
}
return 0;
}
