#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 3e2;
typedef long long ll;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
vector<int> asked_values[MAXN];
int cnt = 0;
vector<int> ASK(int i){
vector<int> res;
if (asked_values[i].empty()){
cnt++;
assert(cnt <= 10000);
res = ask(i);
asked_values[i] = res;
//cout << i << ' ' << res.front() << ' ' << res.back() << endl;
} else res = asked_values[i];
return res;
}
int find_best(int n) {
vector<int> res;
int mx = 0;
int pos = 0;
while (pos < 500){
ASK(pos);
res = ASK(pos);
if (res[0] + res[1] == 0) return pos;
mx = max(mx, res[0] + res[1]);
pos++;
}
while (pos < n){
res = ASK(pos);
if (res[0] + res[1] == 0) return pos;
int nxt = pos + 1;
int l = pos + 1, r = n - 1;
while (l <= r){
int m = (l + r) >> 1;
res = ASK(m);
if (res[0] + res[1] == 0) return m;
if (res[0] + res[1] < mx){
r = m - 1;
nxt = m;
} else {
auto tmp = ASK(pos);
if (res[0] == tmp[0]) l = m + 1, nxt = m + 1; else
r = m - 1, nxt = m - 1;
}
}
pos = max(pos + 1, nxt);
}
return n / 2;
}
