#include <bits/stdc++.h>
using namespace std;
vector<int> ask(int i);
const int maxn = 2e5 + 5;
vector<int> ans[maxn];
int cnt = 0;
vector<int> qry(int i) {
if (ans[i].size() == 2) return ans[i];
else {
cnt++;
// assert(cnt <= 10000);
return ans[i] = ask(i);
}
}
int find_best(int n) {
int mx = 0;
for (int i=0;i<500;i++) {
int val = qry(i)[0] + qry(i)[1];
if (val == 0) return i;
mx = max(val, mx);
}
assert(cnt == 500);
for (int i=500;i<n;i++) {
vector<int> vec = qry(i);
if (vec[0] + vec[1] == 0) return i;
if (vec[0] + vec[1] == mx) {
int l = i, r = n-1;
if (qry(i+1) == vec && i+2 < n && qry(i+2) == vec) {
while (l < r) {
int mid = (l+r+1)/2;
if (qry(mid) == vec) l = mid;
else r = mid-1;
}
}
i = l;
}
}
return 0;
}
