#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());
int foo, hoo;
vector<int> asked_values[MAXN];
int calls_count = 0;
void ASK(int i){
vector<int> res;
if (asked_values[i].empty()){
calls_count++;
res = ask(i);
//cout << i << ' ' << res.front() << ' ' << res.back() << endl;
} else res = asked_values[i];
foo = res.front();
hoo = res.back();
asked_values[i] = res;
assert(calls_count <= 10000);
}
int find_best(int n) {
int mx = 0;
for (int i = 0; i < 1000; i++){
int x = rng() % n;
ASK(x);
if (foo + hoo == 0) return x;
mx = max(mx, foo + hoo);
}
int cur = 0;
for (int i = 0; i < n; i++){
int l = i, r = n - 1;
int idx = n;
while (l <= r){
int m = (l + r) >> 1;
ASK(m);
if (foo + hoo == 0) return m;
if (foo + hoo < mx) idx = m;
if (foo > cur){
r = m - 1;
} else l = m + 1;
}
i = idx;
cur++;
}
return 0;
}
