#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
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]);
}
set < int > ava, del;
vector < int > Del;
vector < int > mark[1001];
void correct(int pos, int last = -1){
// if (pos == 99999) cerr << last _ byl[pos] _ ty[pos].F _ ty[pos].S << endl;
if (last == -1){
if (Del.size() == 0) return;
// cout << pos _ byl[pos] _ Del.back() << endl;
for (auto last : Del){
// cout << last << " ";
if (last >= byl[pos]) continue;
int pp = lower_bound(mark[last].begin(), mark[last].end(), pos) - mark[last].begin();
byl[pos] = last;
ty[pos] = {ty[pos].F - pp, ty[pos].S - (mark[last].size() - pp)};
// if (pos == 99999)
// cerr << last _ pos _ mark[last].size() _ pp _ ty[pos].F _ ty[pos].S << endl;
}
// cout<<endl;
return;
}
int pp = lower_bound(mark[last].begin(), mark[last].end(), pos) - mark[last].begin();
byl[pos] = last;
ty[pos] = {ty[pos].F - pp, ty[pos].S - (mark[last].size() - pp)};
}
void solve(int l, int r, int nsum){
if (l + 1 >= r){
for (; l <= r; ++l){
if (byl[l]) continue;
ty[l] = Ask(l);
byl[l] = ty[l].F + ty[l].S;
}
return;
}
int mid = (l + r) >> 1;
int m1 = mid, m2 = mid;
for (; m1 >= l; --m1){
ty[m1] = Ask(m1);
byl[m1] = ty[m1].F + ty[m1].S;
correct(m1);
if (byl[m1] == nsum) break;
}
for (; m2 <= r; ++m2){
ty[m2] = Ask(m2);
byl[m2] = ty[m2].F + ty[m2].S;
correct(m2);
if (byl[m2] == nsum) break;
}
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);
}
mt19937_64 gen1(chrono::high_resolution_clock::now().time_since_epoch().count());
int find_best(int n) {
int bg = 750; // 370
int cnst1 = min(n, bg);
int cnst2 = min(n, bg);
int mx = -1;
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;
mx = max(mx, sum);
if (sum > bg) break;
}
for (int i = n - 1; i >= n - cnst2; --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;
if (sum > bg || sum == mx) break;
}
int last = -1;
while(true){
if (ava.size() == 0) break;
int x = (*ava.rbegin());
// cout << ava.size() _ x _ byl[99999] << endl;
del.insert(x);
Del.pb(x);
ava.erase(x);
for (int i = 0; i < n; ++i)
if (byl[i] == x){
mark[x].pb(i);
}
for (int i = 0; i < n; ++i)
if (byl[i] > x){
correct(i, x);
}
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;
}
// cerr << x _ lef _ rig _ all << endl;
if (lef >= rig){
cout << "BUG" << endl;
exit(0);
}
solve(lef, rig, x);
last = x;
for (int i = 0; i < n; ++i){
if (byl[i] && !del.count(byl[i]) && !ava.count(byl[i])){
ava.insert(byl[i]);
// cout << i _ byl[i] << "\n";
}
}
// cout<<endl;
}
int ans = -1, cnt = 0;
for (int i = 0; i < n; ++i)
if (byl[i] == 0 && used[i]){
// cout << i << endl;
++cnt;
ans = i;
}
if (cnt != 1){
cout << "CNT bug" << cnt << endl;
}
return ans;
}
