#include<bits/stdc++.h>
using namespace std;
std::vector<int> ask(int i);
const int MAXN = 2e5;
int Ans;
vector<int> A[MAXN];
bool answered[MAXN];
bool Found;
vector<int> ASK(int x) {
if(!answered[x]) {
A[x] = ask(x);
if(A[x][0] + A[x][1] == 0) {
Ans = x;
Found = true;
}
answered[x] = true;
}
return A[x];
}
void solve(int l, int r) {
if(l == r || Found) {
return;
}
int mid = (l + r) / 2;
vector<int> a = ASK(mid), b = ASK(l), c = ASK(r);
if(a[0] + a[1] == b[0] + b[1] && a[0] - b[1] > 0) {
solve(l, mid - 1);
}
if(a[0] + a[1] == c[0] + c[1] && c[0] - a[1] > 0) {
solve(mid + 1, r);
}
}
int find_best(int n) {
for(int i = 0; i < MAXN; i++) {
A[i].resize(2);
}
solve(0, n - 1);
return Ans;
}
