#include<bits/stdc++.h>
using namespace std;
#include "prize.h"
#define pb push_back
#define sz(a) (int)((a).size())
const vector<int> good = {0, 0};
constexpr int maxn = 2e5;
int base, N;
int solve(vector<int>& v, int l, int r) {
if(!sz(v)) return -1;
if(sz(v) == 1) {
if(ask(v[0]) == good) return v[0];
return -1;
}
// printf("l, r == %d %d %d %d\n", l, r, v[0], v.back());
// for(int x : v)
// printf("%d ", x);
// printf("\n");
int m = sz(v)/2;
vector<int> a, b;
for(int i = 0; i < m; i++)
a.pb(v[i]);
vector<int> res = ask(v[m]);
if(res == good) return v[m];
if(res[0]+res[1] == base) {
// printf("v %d\n", v[m]);
for(int i = m; i < sz(v); i++)
b.pb(v[i]);
if(res[0] - l) {
int ans = solve(a, l, res[1]);
if(ans != -1) return ans;
}
if(r - res[1]) {
int ans = solve(b, res[0], r);
if(ans != -1) return ans;
}
} else {
int seen = 1, p = v[m]+1;
bool ok = 0;
while(p <= v.back()) {
// printf("p %d\n", p);
res = ask(p);
if(res == good) return p;
if(res[0]+res[1] == base) {
for(int i = p+1; i <= v.back(); i++)
b.pb(i);
if(res[0] - l - seen) {
int ans = solve(a, l, res[1]+seen);
if(ans != -1) return ans;
}
if(r - res[1]) {
int ans = solve(b, res[0], r);
if(ans != -1) return ans;
}
ok = 1;
}
++p, ++seen;
}
if(!ok) {
int r = seen+(v.back()==N-1?0:(ask(v.back()+1)[1]));
// if(r + l != base) {
int ans = solve(a, l, r);
if(ans != -1) return ans;
// }
}
}
return -1;
}
int find_best(int n) {
N = n;
int last = 0;
// base = 3;
for(int i = 0; i < min(475, n); i++) {
vector<int> opa = ask(i);
if(opa == good) return i;
if(opa[0]+opa[1] >= base)
base = opa[0]+opa[1];
}
vector<int> a;
for(int i = 0; i < n; i++)
a.pb(i);
return solve(a, 0, 0);
}
