#include <iostream>
#include <vector>
using namespace std;
std::vector<int> ask(int i);
vector<int> res, dp[200010];
int ans, maxx, cnt;
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) {
for (int i = 0; i < min(450,n); i++) {
res = ask(i);
maxx = max(maxx,res[0]+res[1]);
}
dp[0] = {0,maxx};
dp[n+1] = {maxx,0};
solve(1,n);
return ans;
}
