// 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 = 1000, mod = 1e9 + 7, inf = 1e9 + 10;
int MX;
int CNT = 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){
if(r-l <= 0)
return;
int mid = (l+r) >> 1;
int pos = mid;
while(pos < r){
pii p = ASK(pos);
if(p.F + p.S != MX){
pos++;
}
else{
if(p.S > 0)
go(pos + 1, r);
break;
}
}
pos = mid-1;
while(pos >= l){
pii p = ASK(pos);
if(p.F + p.S != MX){
pos--;
}
else{
if(p.F > 0)
go(l, pos);
break;
}
}
}
int ITER = 0;
int find_best(int n){
assert(++ITER == 1);
try{
for(int i = 0; i < SQ; i++){
pii p = ASK(i);
MX = max(MX, p.F + p.S);
}
go(0, n);
}
catch(int ans){
return ans;
}
assert(0);
}
