#include "prize.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vii> vvii;
typedef vector<vll> vvll;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
#define ffor(i, a, b) for (ll i = (a); i < (ll)(b); i++)
#define fford(i, a, b) for (ll i = (a); i > (ll)(b); i--)
#define rep(i, n) ffor(i, 0, n)
#define forin(x, a) for (auto &x: a)
#define all(a) a.begin(), a.end()
map<int, pii> memo;
pii ask2(int i) {
if (memo.find(i) == memo.end()) {
auto res = ask(i);
memo[i] = {res[0], res[1]};
}
return memo[i];
}
int find_best(int n) {
if (n <= 5000) {
rep(i, n) {
auto res = ask2(i);
if (!res.first && !res.second) {
return i;
}
}
}
int a = n / 2, b = rand() % n, c = rand() % n;
while (b == a) {
b = rand() % n;
}
while (c == a || c == b) {
c = rand() % n;
}
auto res1 = ask2(a), res2 = ask2(b), res3 = ask2(c);
if (!res1.first && !res1.second) {
return a;
}
if (!res2.first && !res2.second) {
return b;
}
if (!res3.first && !res3.second) {
return c;
}
int expcount = max(max(res1.first + res1.second, res2.first + res2.second), res3.first + res3.second);
int found = 0;
while (res1.first + res1.second != expcount) {
a++;
found++;
res1 = ask2(a);
if (!res1.first && !res1.second) {
return a;
}
}
deque<tuple<int, int, int, int, int>> segs = {{0, n / 2 - 1, res1.first - found, 0, found + res1.second}, {a + 1, n - 1, res1.second, res1.first, 0}};
while (!segs.empty()) {
int lo, hi, cnt, tol, tor, l, r;
tie(lo, hi, cnt, tol, tor) = segs.front();
segs.pop_front();
int med = (lo + hi) / 2;
tie(l, r) = ask2(med);
if (!l && !r) {
return med;
}
int found2 = 0;
while (l + r != expcount && med < hi) {
med++;
found2++;
tie(l, r) = ask2(med);
if (!l && !r) {
return med;
}
}
if (l + r != expcount) {
if (cnt - found2 > 0) {
segs.emplace_back(lo, (lo + hi) / 2 - 1, cnt - found2, tol, tor + found2);
}
} else {
if (l - found2 - tol > 0) {
segs.emplace_back(lo, (lo + hi) / 2 - 1, l - found2 - tol, tol, found2 + r);
}
if (r - tor > 0) {
segs.emplace_back(med + 1, hi, r - tor, l, tor);
}
}
}
return 0;
}
