#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 55;
const int K = N/500;
vector<int>memo[N]; int done[N];
int Q;
set<int>alive;
void del(int l, int r) {
while (alive.size()) {
auto it = alive.lower_bound(l);
if (*it <= r) alive.erase(it);
else break;
}
}
set<int>pos[N];
vector<int>qwe(int i) {
if (done[i]) return memo[i];
Q++; while (Q > 10000);
done[i] = 1; memo[i] = ask(i);
int x = memo[i][0] + memo[i][1];
if (x == 0) return memo[i];
if (0) {
auto it = pos[x].lower_bound(i);
if (it == pos[x].end() && memo[i][1] == 0) del(i, N);
if (it != pos[x].end() && memo[i][1] == memo[*it][1]) del(i, *it);
if (it == pos[x].begin() && memo[i][0] == 0) del(0, i);
if (it != pos[x].begin() && memo[i][0] == memo[*prev(it)][0]) del(*prev(it), i);
pos[x].insert(i);
}
return memo[i];
}
int solve(int need, int ql, int qr, int mx) {
if (ql > qr) return -1;
int l = ql, r = qr, ret = -1;
while (l <= r) {
int mid = (l + r) >> 1;
auto it = alive.lower_bound(mid);
int m = -1;
if (it != alive.end() && *it <= r) m = *it;
else if (it != alive.begin() && *prev(it) >= l && *prev(it) <= r) m = *prev(it);
else return -1;
if (qwe(m)[0] + qwe(m)[1] == 0) return m;
if (qwe(m)[0] + qwe(m)[1] != mx) ret = m, r = m - 1;
else if (qwe(m)[0] == need) l = m + 1;
else r = m - 1;
}
if (ret == -1) return -1;
r = ret;
while (r <= qr) {
if (qwe(r)[0] + qwe(r)[1] == 0) return r;
if (qwe(r)[0] + qwe(r)[1] == mx) break;
++r;
}
return solve(qwe(r)[0], r, qr, mx);
}
int find_best(int n) {
for (int i = 0 ; i < n ; ++ i) alive.insert(i);
if (n <= 10000) {
for (int i = 0 ; i < n ; ++ i) {
if (qwe(i)[0] + qwe(i)[1] == 0) return i;
}
}
vector<int>ids;
int mx = 0;
for (int i = 0 ; i < n - 1 ; i += K) {
if (qwe(i)[0] + qwe(i)[1] == 0) return i;
mx = max(mx, qwe(i)[0] + qwe(i)[1]);
ids.emplace_back(i);
}
if (qwe(n - 1)[0] + qwe(n - 1)[1] == 0) return n - 1;
mx = max(mx, qwe(n-1)[0] + qwe(n-1)[1]);
ids.emplace_back(n - 1);
for (int i = 0 ; i + 1 < (int)ids.size() ; ++ i) {
int x = ids[i], y = ids[i + 1];
while (x <= y) {
if (qwe(x)[0] + qwe(x)[1] == 0) return x;
if (qwe(x)[0] + qwe(x)[1] == mx) break;
++x;
}
while (x <= y) {
if (qwe(y)[0] + qwe(y)[1] == 0) return y;
if (qwe(y)[0] + qwe(y)[1] == mx) break;
--y;
}
if (x > y) continue;
int res = solve(qwe(x)[0], x, y, mx);
if (res != -1) return res;
}
return -1;
}
