// Oh damn! Suddenly you're free to fly...
#include<bits/stdc++.h>
#include "prize.h"
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 2e5 + 10, SQ = 600, mod = 1e9 + 7, inf = 1e9 + 10;
int MX;
int CNT = 0;
int GOOD = 0;
pii ASK(int pos){
assert(++CNT <= 10000);
vector<int> v = ask(pos);
if(v[0] == 0 && v[1] == 0)
throw pos;
return {v[0], v[1]};
}
void go(int l, int r, int L, int R){
if(r-l <= 0 || L >= R)
return;
int mid = (l+r) >> 1;
pii p = ASK(mid);
if(p.F + p.S == MX){
go(mid+1, r, p.F, R);
go(l, mid, L, p.F);
return;
}
if(++GOOD > SQ){
while(true){
}
}
int pos = mid + 1;
while(pos < r){
pii p = ASK(pos);
if(p.F + p.S != MX){
if(++GOOD > SQ){
while(true){
}
}
pos++;
}
else{
go(pos + 1, r, p.F, R);
break;
}
}
pos = mid-1;
while(pos >= l){
pii p = ASK(pos);
if(p.F + p.S != MX){
if(++GOOD > SQ){
while(true){
}
}
pos--;
}
else{
go(l, pos, L, p.F);
break;
}
}
}
int find_best(int n){
try{
for(int i = 0; i < SQ; i++){
pii p = ASK(i);
MX = max(MX, p.F + p.S);
}
go(0, n, 0, MX);
}
catch(int ans){
return ans;
}
return -1;
}
