#include "prize.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
typedef pair <int, int> PII;
map <int, PII> asked;
bool found;
const int N = 2e5+50;
int ans = -1, n, miniCnt;
PII askPos(int n) {
if (asked.count(n)) return asked[n];
vector <int> res = ask(n);
PII cur = {res[0], res[1]};
if (cur.ff + cur.ss == 0) {
ans = n;
found = 1;
}
return asked[n] = cur;
}
void find(int l, int r, int L, int R) {
if (r < l || found) return;
if (miniCnt == L + R) return;
int m = (l+r)>>1;
int x = m;
PII res;
for (; x <= r && !found; x++) {
res = askPos(x);
if (res.ff + res.ss > miniCnt) {
miniCnt = res.ff + res.ss;
find(0, n-1, 0, 0);
}
if (res.ff + res.ss == miniCnt) break;
}
if (l != r && !found) {
find(l, m-1, L, x - m + res.ss);
find(x+1, r, res.ff, R);
}
}
int find_best(int n1) {
miniCnt = 1;
n = n1;
find(0, n-1, 0, 0);
return ans;
}
