#include "prize.h"
#include "bits/stdc++.h"
using namespace std;
#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
assert(l <= r);
return uniform_int_distribution<int> (l, r)(rng);
}
const int maxn = 2e5 + 5;
const int B = 478;
static int n;
vector<int> que[maxn];
int cnt_asks;
set<int> cnt_rank[maxn];
int id[maxn], cnt_id;
int rev[maxn];
struct fenwick_tree {
int bit[maxn];
void upd(int i, int v) {
++i;
for (; i <= n; i += i & (-i)) bit[i] += v;
}
int get(int i) {
++i;
int ans = 0;
for (; i > 0; i -= i & (-i)) ans += bit[i];
return ans;
}
int get(int l, int r) {
return l > r ? 0 : get(r) - get(l - 1);
}
} bit[6];
vector<int> abc(int i) {
++cnt_asks;
if(que[i].empty()) {
que[i] = ask(i);
cnt_rank[que[i][0] + que[i][1]].insert(i);
if (!id[que[i][0] + que[i][1]]) {
id[que[i][0] + que[i][1]] = ++cnt_id;
rev[cnt_id] = que[i][0] + que[i][1];
}
bit[id[que[i][0] + que[i][1]]].upd(i, 1);
}
return que[i];
}
int find_exp(int x, int l, int r) {
int res = 0;
for (int i = 1; i <= cnt_id; ++i) {
if (rev[i] < x) {
res += bit[i].get(l, r);
}
}
return res;
}
int ans, mx;
void calc(int l, int r) {
if (r - l < 2 || ans != -1) return;
if (que[r][0] - que[l][0] == 0) return;
int mid = l + (r - l) / 3 * 2;
int pl = mid, pr = mid;
bool skip_left = 0, skip_right = 0;
while (pr < r) {
abc(pr);
int sum = que[pr][0] + que[pr][1];
if (sum == 0) {
ans = pr;
return;
}
if ((int)cnt_rank[sum].size() > 1) {
auto it = cnt_rank[sum].upper_bound(pr);
if (it != cnt_rank[sum].end() and que[*it][0] - que[pr][0] == find_exp(sum, pr, *it)) {
skip_right = 1;
break;
}
it = cnt_rank[sum].lower_bound(pr);
if (it != cnt_rank[sum].begin()) {
--it;
if (*it < l and que[pr][0] - que[*it][0] == find_exp(sum, *it, pr)) {
skip_left = 1;
}
}
}
if (sum == mx) break;
++pr;
}
if (!skip_right) {
calc(pr, r);
}
if (skip_left) return;
while (pl > l) {
abc(pl);
int sum = que[pl][0] + que[pl][1];
if (sum == 0) {
ans = pl;
return;
}
if ((int)cnt_rank[sum].size() > 1) {
auto it = cnt_rank[sum].lower_bound(pl);
if (it != cnt_rank[sum].begin()) {
--it;
if (que[pl][0] - que[*it][0] == find_exp(sum, *it, pl)) {
skip_left = 1;
break;
}
}
}
if (que[pl][0] + que[pl][1] == mx) break;
--pl;
}
if (!skip_left) {
calc(l, pl);
}
}
int find_best(int N) {
n = N;
ans = -1;
int x = min(n - 1, B);
for (int i = 0; i <= x; ++i) {
vector<int> cur = abc(i);
if (cur[0] + cur[1] == 0) return i;
mx = max(mx, cur[0] + cur[1]);
}
while (x >= 0) {
if (que[x][0] + que[x][1] == mx) break;
--x;
}
int lst = n - 1;
while (lst >= 0) {
vector<int> cur = abc(lst);
if (cur[0] + cur[1] == 0) return lst;
if (cur[0] + cur[1] == mx) break;
--lst;
}
calc(x, lst);
return ans;
}
