#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mod 1000000007
#define h1 7897897897897897
#define h2 7897466719774591
#define b1 98762051
#define b2 98765431
#define inf 1000000000
#define pi 3.1415926535897932384626
#define LMAX 9223372036854775807
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pii>
#define SET(a, b) memset(a, b, sizeof(a))
#define all(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
#define SQ 450
vi mem[200005];
int prize = -1, maxx;
void solve(int l, int r, int aim) {
if (l > r || aim == 0 || prize != -1) return;
//cout << l << ' ' << r << ' ' << aim << endl;
int mid = (l + r) >> 1;
vi res = mem[mid];
if (res.empty()) {
mem[mid] = ask(mid);
res = mem[mid];
}
//cout << res[0] << " " << res[1] << endl;
if (res[0] + res[1] == 0) {
prize = mid;
return;
}
if (res[0] + res[1] == maxx) {
//cout << "hello " <<mem[l-1][0] << endl;
solve(l, mid - 1, res[0] - mem[l-1][0]);
solve(mid + 1, r, aim - (res[0] - mem[l-1][0]));
} else {
int pointer = mid;
while (pointer < r) {
pointer++;
res = mem[pointer];
if (res.empty()) {
mem[pointer] = ask(pointer);
res = mem[pointer];
}
if (res[0] + res[1] == 0) {
prize = pointer;
return;
}
if (res[0] + res[1] == maxx) {
solve(l, mid - 1, res[0] - mem[l-1][0] - (pointer - mid));
solve(pointer + 1, r, aim - (res[0] - mem[l-1][0]));
return;
}
pointer++;
}
solve(l, mid - 1, aim - (r - mid + 1));
}
}
int find_best(int n) {
if (n <= 5000) {
FOR(i, 0, n-1) {
vi tmp = ask(i);
if (tmp[0] + tmp[1] == 0) return i;
}
}
//----
int cnt = 0;
for (int i = 0; i < n; i += 500) {
cnt++;
mem[i] = ask(i);
if (mem[i][0] + mem[i][1] == 0) return i;
maxx = max(maxx, mem[i][0] + mem[i][1]);
}
FOR(i, 0, n-1) {
if (i % 500 == 0) continue;
if (cnt >= 500) break;
cnt++;
mem[i] = ask(i);
if (mem[i][0] + mem[i][1] == 0) return i;
maxx = max(maxx, mem[i][0] + mem[i][1]);
}
vi seg;
for (int i = 0; i < n; ) {
while (i < n) {
if (mem[i].empty()) {
mem[i] = ask(i);
if (mem[i][0] + mem[i][1] == 0) return i;
}
if (mem[i][0] + mem[i][1] == maxx) {
break;
}
i++;
}
if (i < n) seg.pb(i);
i++;
while (i < n) {
if (i % 500 == 0) break;
i++;
}
}
int last = -1, sum = 0;
for (int pos: seg) {
///cout << pos << ": " << mem[pos][0] - sum << endl;
solve(last + 1, pos - 1, mem[pos][0] - sum);
sum = mem[pos][0];
last = pos;
}
solve(last + 1, n - 1, mem[last][1]);
return prize;
}
