#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){
if(r<l) 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);
return;
}
solve(l,mid-1);
pos.pb(mid);
if(R[pos.back()]>0){
solve(mid+1,r);
}
}
else{
vector<int>add;
add.pb(mid);
for(int i=mid-1;i>=l;i--){
vector<int>rs=ask(i);
L[i]=rs[0];
R[i]=rs[1];
if(L[i]+R[i]<mx){
add.pb(i);
continue;
}
else{
if(L[i]==L[pos.back()]){
for(int j=l;j<=i;j++){
L[j]=L[i];
R[j]=L[j];
pos.pb(j);
}
return;
}
else{
solve(l,i-1);
}
break;
}
}
reverse(all(add));
for(int i:add) f.pb(i);
if(R[pos.back()]>0){
solve(mid+1,r);
}
}
return;
}
int find_best(int n){
N=n;
for(int i=0;i<min(500,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(500,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);
}
for(int i:f){
if(L[i]+R[i]==0){
return i;
}
}
return 0;
}
