#include"prize.h"
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> seg(200005, {-1, -1});
int ans = -1, mx = 0;
void check(int i) {
if (seg[i][0] == seg[i][1] && seg[i][0] == 0) {
ans = i;
}
}
void Ask(int i) {
if (seg[i][0] == -1) {
seg[i] = ask(i);
mx = max(mx, seg[i][0]+seg[i][1]);
check(i);
}
}
void calc(int l, int r, int xl, int xr) {
if (ans != -1) {
return;
}
if (l == r) {
Ask(l);
return;
}
if (xl+xr >= mx) {
return;
}
int m1 = (l+r)/2, m2 = (l+r)/2;
for (; m1 > l; m1--) {
Ask(m1);
if (ans != -1) {
return;
}
if (seg[m1][0]+seg[m1][1] == mx) {
break;
}
}
calc(l, m1, xl, seg[m1][1]);
if (ans != -1) {
return;
}
for (; m2 < r; m2++) {
Ask(m2);
if (ans != -1) {
return;
}
if (seg[m2][0]+seg[m2][1] == mx) {
break;
}
}
calc(m2, r, seg[m2][0], xr);
}
int find_best(int n) {
for (int i = 0; i < sqrt(n); i++) {
Ask(i);
}
calc(0, n-1, 0, 0);
return ans;
}
