#include <bits/stdc++.h>
#include "prize.h"
typedef std::pair<int,int> pii;
int diamante=-1;
int N;
pii pergunta(int p){
auto x = ask(p-1);
if(!(x[0]+x[1])){
diamante=p;
}
return {x[0],x[1]};
}
int range = 450;
int maxa=0;
void cdc(int l=1,int r=N,int left=0,int right=0){
if(l>r)return;
if(left+right==maxa)return;
int curl=0,curr=1;
int m = (l+r)/2;
int computou=0;
int size=r-l+1;
pii ans;
int lf=m,rf=m;
int split=m;
while(computou!=size){
if(curl<curr){
int novpos = m-curl;
++curl;
if(novpos<l){continue;}
lf=novpos;
split=novpos;
ans = pergunta(novpos);
if(ans.first+ans.second==maxa)break;
}else {
int novpos = m+curr;
++curr;
if(novpos>r){continue;}
rf=novpos;
split=novpos;
ans = pergunta(novpos);
if(ans.first+ans.second==maxa)break;
}
++computou;
}
if(split==lf)
cdc(l,lf-1,left,ans.second);
else if(split==rf){
cdc(l,lf-1,left,ans.second+computou);
}else assert(0);///Erro! Eh na direita ou esquerda
if(split==lf)
cdc(rf+1,r,ans.first+computou,right);
else if(split==rf){
cdc(rf+1,r,ans.first,right);
}else assert(0);///Erro! Eh na direita ou esquerda
}
int find_best(int n) {
assert(0);
N=n;
range=std::min(range-1,N);
for(int i=1;i<range;++i){
pii u = pergunta(i);
maxa=std::max(u.first+u.second,maxa);
}
cdc(range,N,0,0);
assert(diamante!=-1);
return diamante-1;
}
