#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()
void solve(int l,int r,int &n,vector<int>&L,vector<int>&R,int &mx,vector<int>&pos,vector<int>&f){
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,n,L,R,mx,pos,f);
return;
}
solve(l,mid-1,n,L,R,mx,pos,f);
pos.pb(mid);
solve(mid+1,r,n,L,R,mx,pos,f);
}
else{
solve(l,mid-1,n,L,R,mx,pos,f);
f.pb(mid);
solve(mid+1,r,n,L,R,mx,pos,f);
}
return;
}
int find_best(int n){
vector<int>L(n),R(n),pos,f;
int mx=0;
for(int i=0;i<min(500,n);i++){
vector<int>res=ask(i);
L[i]=res[0];
R[i]=res[0];
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,n,L,R,mx,pos,f);
}
for(int i:f){
vector<int>res=ask(i);
if(res[0]+res[1]==0){
return i;
}
}
return 0;
}
// 1 2 5 26 677
