#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
#define vt vector
#define INF 0x3f3f3f3f
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rep(i,x) for(int (i) = 0;(i) < (x); (i)++)
#define MOD 1000000007
typedef vt<int> vi;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
pii got[200005];
int fotal = 0;
int consum(int l, int r, int minl, int minr) {
if (r < l)
return -1;
int mid = (l + r) >> 1;
vi a;
if (got[mid] != make_pair(-1, -1))
a = {got[mid].first, got[mid].second};
else
a = ask(mid);
if (a[0] + a[1] == fotal) {
a[0] -= minl;
a[1] -= minr;
int x = -1, y = -1;
if (a[0] != 0)
x = consum(l, mid - 1, minl, a[1] + minr);
if (x != -1)
return x;
if (a[1] != 0)
y = consum(mid + 1, r, minl + a[0], minr);
return max(x, y);
} else if (a[0] + a[1] == 0) {
return mid;
} else {
int cur1 = mid - 1;
int cur2 = mid + 1;
int has = 1;
while (cur2 <= r) {
if (got[cur2] != make_pair(-1, -1))
a = {got[cur2].first, got[cur2].second};
else
a = ask(cur2);
if (a[0] + a[1] == fotal) {
int x = -1, y = -1;
if (a[0] - minl - has != 0)
x = consum(l, mid - 1, minl, a[1] + has);
if (x != -1)
return x;
if (a[1] - minr != 0)
y = consum(cur2 + 1, r, a[0], minr);
return max(x, y);
} else if (a[0] + a[1] == 0) {
return cur2;
} else {
cur2++;
has++;
}
}
while (cur1 >= l) {
if (got[cur1] != make_pair(-1, -1))
a = {got[cur1].first, got[cur1].second};
else
a = ask(cur1);
if (a[0] + a[1] == fotal) {
if (a[0] - minl != 0)
return consum(l, cur1 - 1, minl, a[1]);
else
return -1;
} else if (a[0] + a[1] == 0) {
return cur1;
} else {
cur1--;
}
}
return -1;
}
}
int find_best(int n) {
vi arr(n);
for (int i = 0; i < n; i++) {
got[i] = {-1, -1};
arr[i] = i;
}
random_shuffle(all(arr));
int k = sqrt(n) + 2;
for (int i = 0; i < k; i++) {
int j = arr[i];
vi a = ask(j);
got[j] = {a[0], a[1]};
if (a[0] + a[1] == 0)
return j;
if (a[0] + a[1] > fotal)
fotal = a[0] + a[1];
}
return consum(0, n - 1, 0, 0);
}
