#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int mxn = 2e5 + 10;
int L, R;
vector<int> know[mxn];
vector<int> get(int x) {
if (know[x].size()) return know[x];
return know[x] = ask(x);
}
void solve(int l, int r) {
if (l > R || r < L || l > r) return;
if (get(l)[0] + get(l)[1] == 0) {
L = R = l;
return;
}
if (get(r)[0] + get(r)[1] == 0) {
L = R = r;
return;
}
if (r - l <= 1) return;
vector<int> valL = get(l), valR = get(r);
int x = uniform_int_distribution<int> (l + 1, r - 1)(rng);
vector<int> valX = get(x);
int sumL = valL[0] + valL[1], sumR = valR[0] + valR[1], sumX = valX[0] + valX[1];
if (sumX == 0) {
L = R = x;
return;
}
if (valX[0] + valX[1] == 1) {
if (valX[0] == 0) {
L = max(L, x + 1);
solve(x + 1, r - 1);
}
else {
R = min(R, x - 1);
solve(l + 1, x - 1);
}
}
else {
if (sumX < sumL && sumX < sumR) {
if (valX[0] > valX[1]) solve(l, x - 1);
else solve(x + 1, r);
}
else solve(l + 1, r - 1);
}
}
int find_best(int n) {
L = 0, R = n - 1;
solve(L, R);
return L;
}
