/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
#pragma GCC optimize ("unroll-loops")
using namespace std;
typedef long long ll;
vector <int> ask (int i);
vector <int> L, R;
void discover (int i) {
if (L[i] == -1) {
vector <int> resp = ask(i);
L[i] = resp[0];
R[i] = resp[1];
}
}
map <int, map <int, int>> mp;
int solve (int l, int r) {
int mid = (l + r) / 2;
discover(mid);
int cntLess = L[mid] + R[mid];
if (cntLess == 0) {
return mid;
}
mp[cntLess][mid] = L[mid];
map <int, int> :: iterator it = mp[cntLess].find(mid);
if (l < mid && (it == mp[cntLess].begin() || L[mid] - prev(it)->second > 0)) {
int sl = solve(l, mid - 1);
if (sl != -1) {
return sl;
}
}
if (mid + 1 < r && (next(it) == mp[cntLess].end() || next(it)->second - L[mid] > 0)) {
int sr = solve(mid + 1, r);
if (sr != -1) {
return sr;
}
}
return -1;
}
int find_best (int n) {
L = vector <int> (n, -1);
R = vector <int> (n, -1);
return solve(0, n - 1);
}
