#include "prize.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
using i64 = long long;
using d64 = long double;
using pi = pair<int, int>;
using pli = pair<i64, i64>;
using ti = tuple<int, int, int>;
using tli = tuple<i64, i64, i64>;
#define iterall(cont) cont.begin(), cont.end()
#define prec(n) setprecision(n) << fixed
vector<vector<int>> cache;
vector<int> neoask(int i) {
if (cache[i].empty()) return cache[i] = ask(i);
return cache[i];
}
int minDeter = 0;
void solve(int s, int e, vector<bool> &mask) {
if (s > e) return;
auto vs = neoask(s);
if (vs[0] + vs[1] != minDeter) {
mask[s] = true;
solve(s + 1, e, mask);
return;
}
auto ve = neoask(e);
if (ve[0] + ve[1] != minDeter) {
mask[e] = true;
solve(s, e - 1, mask);
return;
}
if (e - s <= 1) return;
if (vs[0] == ve[0]) return;
int m = (s + e) >> 1;
auto vm = neoask(m);
if (vm[0] + vm[1] != minDeter) mask[m] = true;
solve(s, m, mask);
solve(m, e, mask);
}
int find_best(int n) {
if (n <= 5000) {
for (int i = 0; i < n; i++) {
auto v = ask(i);
if (v[0] + v[1] == 0) return i;
}
}
vector<bool> mask(n);
cache.resize(n);
// 473번 해보기
random_device rd;
mt19937 gen(rd());
vector<int> shu;
for (int i = 0; i < n; i++) shu.emplace_back(i);
shuffle(iterall(shu), gen);
for (int j = 0; j < 473; j++) {
int i = shu[j];
cache[i] = ask(i);
minDeter = max(minDeter, cache[i][0] + cache[i][1]);
}
solve(0, n - 1, mask);
for (int i = 0; i < n; i++) {
if (!mask[i]) continue;
auto v = neoask(i);
if (v[0] + v[1] == 0) return i;
}
return 0;
}
