#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN=2e5;
int n, a, ft[mxN+1];
vector<int> v;
bool d[mxN];
void upd(int i) {
for(++i; i<=n; i+=i&-i)
++ft[i];
}
int qry(int i) {
int r=0;
for(; i; i-=i&-i)
r+=ft[i];
return r;
}
int dc(int l=0, int r=n-1, int sl=0, int sr=a) {
if(l>r)
return -1;
int ml=(l+r)/2, mr=ml+1, t=0;
vector<int> b;
while(1) {
//cout << l << " " << r << " " << sl << " " << sr << " " << ml << " " << mr << endl;
if(qry(r+1)-qry(l)>=sr-sl)
return -1;
int m=t?mr++:ml--;
t^=1;
if(d[m])
continue;
b=ask(m);
int c=b[0]+b[1];
if(!c)
return m;
if(c>a) {
a=c;
for(int vi : v) {
d[vi]=1;
upd(vi);
}
v.clear();
return dc();
}
if(c==a) {
v.push_back(m);
if(t) {
b[1]=b[0]+(mr-ml-2);
} else {
b[1]=b[0];
b[0]-=(mr-ml-2);
}
break;
}
if(c<a) {
d[m]=1;
upd(m);
}
}
int rl=dc(l, ml, sl, b[0]), rr=-1;
//cout << "g " << l << " " << r << " " << sl << " " << sr << " " << rl << endl;
if(rl<0)
rr=dc(mr, r, b[1], sr);
return max(rl, rr);
}
int find_best(int N) {
n=N;
vector<int> b=ask(n-1);
a=b[0]+b[1];
return a?dc():n-1;
}
