#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;
int ans;
bool found;
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;
}
int middle(PII&a, PII&b) {
return abs(a.ff - b.ff);
}
int sum(PII&a) {
return a.ff + a.ss;
}
int find_best(int n) {
found = 0;
int m = 200, st = 0, miniCnt = 0;
PII last;
for (int i = 0; i < m && !found; i++) {
PII cur = askPos(i);
int curSum = sum(cur);
if (curSum > miniCnt) miniCnt = curSum;
if (curSum == miniCnt) {
last = cur;
st = i;
}
}
int jump = 16, jumped = 0, addPos = 0;
map <int, int> jumpIdx;
while(st < n && jump >= 0 && !found) {
if (st + (1<<jump) >= n) {
jump--;
continue;
}
int asking = st + (1<<jump) + addPos;
PII cur = askPos(asking);
int curSum = sum(cur);
int mid = middle(last, cur);
if (miniCnt != curSum) {
jumped++;
if (jumpIdx.count(jumped) && jumpIdx[jumped] > asking) {
st = jumpIdx[jumped]+1;
addPos = 0;
jumped = 0;
jump = 16;
continue;
}
addPos--;
continue;
} else {
jumpIdx[mid] = asking;
}
if (mid == 0 && miniCnt == curSum) {
st += (1<<jump);
continue;
}
jump--;
}
return ans;
}
