#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
int L[200000],R[200000],tree[1<<19];
void update(int x){
x+=1<<18;
while(x){
tree[x]++;
x/=2;
}
}
int calc(int l,int r){
l+=1<<18;
r+=1<<18;
int a=0;
while(l<r){
if(l&1)a+=tree[l];
if(~r&1)a+=tree[r];
l=(l+1)/2;
r=(r-1)/2;
}
if(l==r)a+=tree[l];
return a;
}
int find_best(int n){
for(int i=0;i<n;i++){
L[i]=R[i]=-1;
}
int s=-1;
for(int i=0;i<n;i++){
vector<int>v=ask(i);
L[i]=v[0];
R[i]=v[1];
if((v[0]+v[1])*2<n){
s=(v[0]+v[1]);
break;
}
}
assert(s!=-1);
for(int i=0;i<s;i++){
int l=-1;
int r=n-1;
while(l+1!=r){
int m=(l+r)/2;
if(L[m]==-1){
vector<int>v=ask(m);
L[m]=v[0];
R[m]=v[1];
}
if(L[m]+R[m]!=s){
r=m;
}
else if(L[m]-calc(0,m)>0){
r=m;
}
else{
l=m;
}
}
if(L[r]==-1){
vector<int>v=ask(r);
L[r]=v[0];
R[r]=v[1];
}
update(r);
if(L[r]==0&&R[r]==0){
return r;
}
}
return -1;
}
