#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 = -1;
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 = min(n, 500), st = 0, end = n - 1, miniCnt = 0;
PII A, B;
for (int i = 0; i < m && !found; i++) {
int j = i;
PII cur = askPos(j);
int curSum = sum(cur);
if (curSum > miniCnt) miniCnt = curSum;
if (curSum == miniCnt)
st = j;
}
while(st < end && !found) {
A = askPos(st);
int l = st, r = end, res = l;
while(l <= r) {
int mid = (l+r)/2;
PII cur = askPos(mid);
if (A == cur) {
res = max(res, mid);
l = mid+1;
} else {
r = mid-1;
}
}
st = res+1;
bool x = 1;
while(x && !found) {
x = 0;
PII cur = askPos(st);
int curSum = sum(cur);
if (curSum != miniCnt) {
x = 1;
st++;
}
}
}
return ans;
}
