#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];
void ASK(int i){
vector<int> res;
if (asked_values[i].empty()){
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;
}
int find_best(int n) {
int mx = 0;
for (int i = 0; i < min(n, 500); i++){
ASK(i);
if (foo + hoo == 0) return i;
mx = max(mx, foo + hoo);
}
int cur = 0;
for (int i = 0; i < n; i++){
int l = i, r = n - 1;
int nxt = n;
while (l <= r){
int m = (l + r) >> 1;
ASK(m);
if (foo + hoo == 0) return m;
if (foo > cur){
r = m - 1;
} else l = m + 1;
}
i = nxt;
if (i == n) break;
ASK(i);
cur = foo + 1;
}
for (int i = n - 1; i >= n - 200; i--){
if (i < 0) break;
ASK(i);
if (foo + hoo == 0) return i;
}
return n / 2;
}
