#include <bits/stdc++.h>
using namespace std;
vector<int> ask(int i);
int candidate_cnt;
int query(int l, int r, int cnt, int lcnt, int rcnt) {
if (l > r || !cnt) return -1;
int mid = (l+r)/2;
vector<int> res = ask(mid);
if (res[0]+res[1] == 0) return mid;
if (res[0]+res[1] == candidate_cnt) return max(query(l, mid, cnt - (res[1]-rcnt), lcnt, res[1]), query(mid, r, cnt - (res[0]-lcnt), res[0], rcnt));
int midl = mid-1, midr = mid+1;
vector<int> lres, rres;
for (; midl >= l; midl--) {
lres = ask(midl);
if (lres[0]+lres[1] == 0) return midl;
if (lres[0]+lres[1] == candidate_cnt) break;
}
for (; midr <= r; midr++) {
rres = ask(midr);
if (rres[0]+rres[1] == 0) return midr;
if (rres[0]+rres[1] == candidate_cnt) break;
}
return max(query(l, midl, cnt - (lres[1]-rcnt), lcnt, lres[1]), query(midr, r, cnt - (rres[0]-lcnt), rres[0], rcnt));
}
int find_best(int n) {
for (int i = 0; i < min(500, n); i++) {
vector<int> res = ask(i);
candidate_cnt = max(candidate_cnt, res[0]+res[1]);
}
return query(0, n-1, candidate_cnt, 0, 0);
}
