#include<bits/stdc++.h>
#include "prize.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int find_best(int n) {
int cur=n-1;
vector<int> q,nq;
q=ask(cur);
while(q[0]!=0 || q[1]!=0){
int sp=-1;
for(int k=0;cur-(1<<k)>=0;k++){
nq=ask(cur-(1<<k));
if(nq[0]!=q[0] || nq[1]!=q[1]) break;
sp=k;
}
if(sp==-1) cur--,q=nq;
else{
int l=max(0,cur-(1<<(sp+1))),r=cur-(1<<sp);
while(r-l>1){
int mid=(l+r)>>1;
nq=ask(mid);
if(nq[0]!=q[0] || nq[1]!=q[1]) l=mid;
else r=mid;
}
cur=l;
q=ask(cur);
}
}
return cur;
}
