#include <iostream>
#include <vector>
#define f first
#define s second
using namespace std;
std::vector<int> ask(int i);
vector<int> res, dp[200010];
int ans, maxx, pos;
vector<pair<int,int>> rng;
void solve(int l, int r) {
if (l > r) return;
if (dp[l-1] == dp[r+1]) return;
int mid = (l+r)/2, ll, rr;
dp[mid] = ask(mid-1);
if (dp[mid][0]+dp[mid][1] == 0) ans = mid-1;
if (dp[mid][0]+dp[mid][1] == maxx) {
solve(l,mid-1);
solve(mid+1,r);
} else {
ll = mid-1;
while (ll >= l) {
dp[ll] = ask(ll-1);
if (dp[ll][0]+dp[ll][1] == 0) ans = ll-1;
if (dp[ll][0]+dp[ll][1] == maxx) break;
ll--;
}
solve(l,ll-1);
rr = mid+1;
while (rr <= r) {
dp[rr] = ask(rr-1);
if (dp[rr][0]+dp[rr][1] == 0) ans = rr-1;
if (dp[rr][0]+dp[rr][1] == maxx) break;
rr++;
}
solve(rr+1,r);
}
}
int find_best(int n) {
if (n <= 5000) {
for (int i = 0; i < n; i++) {
res = ask(i);
if (res[0]+res[1] == 0) return i;
}
}
rng.push_back({-1,0});
for (int i = 1; i <= 500; i++) {
pos += (n-499)/500;
rng.back().s = pos;
rng.push_back({pos,0});
dp[pos+1] = ask(pos);
maxx = max(maxx,dp[pos+1][0]+dp[pos+1][1]);
}
rng.back().s = n;
dp[0] = {0,maxx};
dp[n+1] = {maxx,0};
for (int i = 0; i < rng.size(); i++) {
int ll = rng[i].f, rr = rng[i].s;
while ((ll < rr-1) && (dp[ll+1][0]+dp[ll+1][1] != maxx)) {
ll++;
dp[ll+1] = ask(ll);
if (dp[ll+1][0]+dp[ll+1][1] == 0) return ll;
}
while ((ll < rr-1) && (dp[rr+1][0]+dp[rr+1][1] != maxx)) {
rr--;
dp[rr+1] = ask(rr);
if (dp[rr+1][0]+dp[rr+1][1] == 0) return rr;
}
solve(ll+2,rr);
}
return ans;
}
