#include <bits/stdc++.h>
using namespace std;
std::vector<int> ask(int i);
const int maxn = 2e5 + 5, INF = 1e9;
int N;
vector<int> ans[maxn];
bool start = false;
int mx = 0;
set<int> s;
map<int,int> MX, MN;
set<int> good;
int mxcnt = 0;
vector<int> qry(int i) {
if (ans[i].size() != 2) ans[i] = ask(i);
if (start){
if (ans[i][0] + ans[i][1] == mx) {
if (!s.count(ans[i][0])) {
s.insert(ans[i][0]);
MX[ans[i][0]] = MN[ans[i][0]] = i;
} else {
MX[ans[i][0]] = max(i, MX[ans[i][0]]);
MN[ans[i][0]] = min(i, MN[ans[i][0]]);
}
} else {
good.insert(i);
}
}
return ans[i];
}
void reset() {
while (s.size()) s.erase(*s.begin());
while (good.size()) good.erase(*good.begin());
MX.clear(); MN.clear();
mxcnt = 0;
s.insert(INF);
good.insert(INF);
for (int i=0;i<N;i++) if (ans[i].size() == 2) {
if (ans[i][0] + ans[i][1] == mx) {
if (!s.count(ans[i][0])) {
s.insert(ans[i][0]);
MX[ans[i][0]] = MN[ans[i][0]] = i;
} else {
MX[ans[i][0]] = max(i, MX[ans[i][0]]);
MN[ans[i][0]] = min(i, MN[ans[i][0]]);
}
} else {
good.insert(i);
}
}
}
int find_best(int n) {
N = n;
// if (n <= 5000) {
// for (int i=0;i<n;i++) {
// if (qry(i)[0] + qry(i)[1] == 0) return i;
// }
// }
start = true;
s.insert(INF);
good.insert(INF);
for (int i=0;i<n;i++) {
vector<int> vec = qry(i);
if (vec[0]+ vec[1] == 0) return i;
if (vec[0] + vec[1] > mx) {mx = vec[0] + vec[1]; reset();}
if (vec[0] + vec[1] == mx) {
int l = i, r = min(i + 1023, n-1);
if (i+1023 < n) {
if (qry(i+1023) == vec) r = n-1;
else if (qry(i+1023)[0] + qry(i+1023)[1] > mx) {
mx = qry(i+1023)[0] + qry(i+1023)[1];
reset();
}
}
if (s.count(vec[0])) l = MX[vec[0]];
if (*s.upper_bound(vec[0]) != INF) r = MN[*s.upper_bound(vec[0])] - 1;
r = min(r, *good.upper_bound(l) - 1);
while (l < r) {
int mid = (l+r+1)/2;
if (qry(mid) == vec) l = mid;
else r = mid-1;
if (qry(mid)[0] + qry(mid)[1] > mx) {
mx = qry(mid)[0] + qry(mid)[1];
reset();
l--;
break;
}
}
i = l;
mxcnt += l - i + 1;
}
}
return 0;
}
