// 100/100
#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
int answer = -1;
map<int, array<int, 2>> memo;
array<int, 2> askme(int i) {
array<int, 2> ans;
if (memo.find(i) != memo.end()) {
ans[0] = memo[i][0];
ans[1] = memo[i][1];
} else {
auto v = ask(i);
ans[0] = v[0];
ans[1] = v[1];
}
memo[i] = {ans[0], ans[1]};
if (ans[0] + ans[1] == 0) answer = i;
return ans;
}
int count(int i) { return askme(i)[0] + askme(i)[1]; }
void findall(int l, int r) {
while (l < r && count(l) != count(r)) {
if (answer != -1) return;
if (count(l) > count(r)) {
--r;
} else {
++l;
}
}
if (l >= r) return;
int cnt = askme(r)[0] - askme(l)[0];
if (cnt <= 0) return;
if (answer != -1) return;
int m = (l + r) / 2;
findall(l, m);
findall(m, r);
}
int find_best(int n) {
findall(0, n-1);
return answer;
}
