#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);
std::cout<<ans.first+ans.second<<"\n";
if(ans.first+ans.second==maxa)break;
}else {
int novpos = m+curr;
++curr;
if(novpos>r){continue;}
rf=novpos;
split=novpos;
ans = pergunta(novpos);
std::cout<<ans.first+ans.second<<"\n";
if(ans.first+ans.second==maxa)break;
}
++computou;
}
if(computou+1>=size)return;
if(split==lf){
cdc(l,lf-1,left,ans.second);
}
else if(split==rf&&lf-1>=l){
/// assert(cheatask(lf-2)[1]==ans.second+computou);
cdc(l,lf-1,left,ans.second+computou);
}else assert(0);///Erro! Eh na direita ou esquerda
if(split==lf&&r>=rf+1){
/// std::cout<<cheatask(rf)[0]<<"!!\n";
/// std::cout<<computou<<" "<<cheatask(rf)[0]<<" "<<ans.first<<" ("<<lf<<" "<<rf<<") "<<l<<" "<<r<<" "<<g[split]<<"\n";
/// assert(ans.first+computou==cheatask(rf)[0]);
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) {
N=n;
range=std::min(range-1,N);
std::vector<int> vals;
for(int i=1;i<range;++i){
pii u = pergunta(i);
maxa=std::max(u.first+u.second,maxa);
vals.push_back(u.first+u.second);
}
int count=0;
for(auto&x:vals)if(x<maxa)++count;
cdc(range,N,count,0);
assert(diamante!=-1);
return diamante-1;
}
