#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int>vi;
typedef pair<int,int>pi;
typedef vector<pi> vpi;
#define pb push_back
#define all(x) x.begin(),x.end()
//#include "grader.cpp"
struct seg{
int sz=1;
vi t;
seg(int n){
while(sz<=2*n)
sz*=2;
t.resize(sz);
}
int query(int i){
i+=sz/2;
while(i){
if(t[i])
return 1;
i/=2;
}
return 0;
}
void update(int l,int r){
for(l+=sz/2,r+=sz/2 +1; l<r; l/=2,r/=2){
if(l&1)t[l++]++;
if (r&1)t[--r]++;
}
}
};
int find_best(int n) {
int sz=30;
vi prv={-1,-1};
vpi segs;
seg st(2e5);
for(int i=0; i<n; i+=sz){
if(st.query(i) || st.query(min(n-1,i+sz)))
break;
vi s=(prv[0]==-1?ask(i):prv),e=ask(min(n-1,i+sz));
if(s[0]==0 && s[1]==0)
return i;
if(e[0]==0 && e[1]==0)
return min(i+sz,n-1);
if(s[0]==0)
st.update(0,i);
if(s[1]==0)
st.update(i,n-1);
if(e[1]==0)
st.update(min(i+sz,n-1),n-1);
if(e[0]==0)
st.update(0,min(i+sz,n-1));
if(e[0]==s[0])
continue;
segs.pb({i,min(i+sz,n-1)});
prv=e;
}
srand(time(0));
random_shuffle(all(segs));
for(pi p:segs){
int l=p.first,r=p.second;
for(int i=l+1; i<r; i++){
if(st.query(i))
continue;
vi v=ask(i);
if(v==vi(2,0))
return i;
if(v[0]==0)
st.update(0,i);
if(v[1]==0)
st.update(i,n-1);
}
}
assert(0);
return -1;
}
