#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define ld long double
#define fi first
#define se second
#define F first
#define S second
#define pii pair < int , int >
#define _ <<" "<<
#define TIME 1.0 * clock() / CLOCKS_PER_SEC
map < int , vector < int > > mp;
const int N = 2e5 + 2;
int byl[N];
pii ty[N];
bool used[N];
int all = 0;
pii Ask(int i){
if (used[i]) return ty[i];
++all;
if (all == 10000){
while(true) continue;
}
auto res = ask(i);
used[i] = 1;
return make_pair(res[0], res[1]);
}
void solve(int l, int r, int nsum){
if (l == r){
if (byl[l]) return;
ty[l] = Ask(l);
byl[l] = ty[l].F + ty[l].S;
return;
}
int mid = (l + r) >> 1;
int m1 = mid, m2 = mid + 1;
for (; m1 >= l; --m1){
if (byl[m1]) continue;
ty[m1] = Ask(m1);
byl[m1] = ty[m1].F + ty[m1].S;
if (byl[m1] == nsum) break;
}
for (; m2 <= r; ++m2){
if (byl[m2]) continue;
ty[m2] = Ask(m2);
byl[m2] = ty[m2].F + ty[m2].S;
if (byl[m2] == nsum) break;
}
// cout << l _ r _ mid _ m1 _ m2 << endl;
if (l <= m1 && ty[l].F != ty[m1].F)
solve(l, m1, nsum);
if (r >= m2 && ty[r].F != ty[m2].F)
solve(m2, r, nsum);
}
int find_best(int n) {
int bg = 570; // 370
int cnst1 = min(n, bg);
int cnst2 = min(n, bg);
set < int > ava, del;
for (int i = 0; i < cnst1; ++i){
auto res = Ask(i);
int sum = res.F + res.S;
if (sum == 0) return i;
ava.insert(sum);
byl[i] = sum;
ty[i] = res;
}
for (int i = n - cnst2; i < n; ++i){
auto res = Ask(i);
int sum = res.F + res.S;
if (sum == 0) return i;
ava.insert(sum);
byl[i] = sum;
ty[i] = res;
}
while(true){
if (ava.size() == 0) break;
int x = (*ava.rbegin());
int lef = n + 1, rig = - 1;
for (int i = 0; i < n; ++i)
if (byl[i] == x){
if (lef == n + 1) lef = i;
rig = i;
}
// cout << lef _ rig << endl;
if (lef == rig){
cout << "BUG" << endl;
exit(0);
}
solve(lef, rig, x);
ava.erase(x);
del.insert(x);
for (int i = 0; i < n; ++i)
if (byl[i] && !del.count(byl[i]))
ava.insert(byl[i]);
}
int ans = -1, cnt = 0;
for (int i = 0; i < n; ++i)
if (byl[i] == 0 && used[i]){
++cnt;
ans = i;
}
if (cnt != 1){
cout << "CNT bug" << endl;
}
return ans;
}
