#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T>
using ordered_set=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
vector<int> mem[200000];
vector<int> Ask(int i){
if (mem[i].size()) return mem[i];
return mem[i]=ask(i);
}
int find_best(int n) {
for (int i=0; i<n; ++i) mem[i].clear();
// if (n<=5000){
// for (int i=0; i<n; ++i){
// auto tmp=Ask(i);
// if (tmp[0]+tmp[1]==0) return i;
// }
// return -1;
// }
int m=n;
int mx=0;
while (m>1){
m=(int)sqrt(m);
mx+=m;
}
vector<pair<int, int>> v(mx);
for (int i=0; i<mx; ++i){
auto tmp=Ask(i);
v[i]={tmp[0], tmp[1]};
if (tmp[0]+tmp[1]==0) return i;
}
int cnt=0;
for (auto &i:v) cnt=max(cnt, i.first+i.second);
ordered_set<int> id;
vector<int> st;
for (int i=0; i<mx; ++i) if (v[i].first+v[i].second!=cnt) id.insert(i);
for (int i=mx; i<n; ++i) st.push_back(i);
auto solve=[&](auto &&self, vector<int> pos, int cc){
if (!cc || pos.empty()) return;
int mid=((int)pos.size()-1)/2;
vector<int> posl, posr;
for (int j:pos){
if (j<pos[mid]) posl.push_back(j);
if (j>pos[mid]) posr.push_back(j);
}
auto tmp=Ask(pos[mid]);
if (tmp[0]+tmp[1]!=cnt){
id.insert(pos[mid]);
pos.erase(pos.begin()+mid);
self(self, pos, cc-1);
// int l=mid, r=mid;
// while (l){
// --l;
// auto tmp2=Ask(pos[l]);
// if (tmp2[0]+tmp2[1]!=cnt) id.insert(pos[l]), posl.pop_back();
// else{
// int cl=tmp2[0]-id.order_of_key(pos[l]);
// int cr=tmp2[1]-((int)id.size()-id.order_of_key(pos[l]));
// self(self, posl, cl);
// self(self, posr, cr);
// return;
// }
// }
// reverse(posr.begin(), posr.end());
// while (r+1<(int)pos.size()){
// ++r;
// auto tmp2=Ask(pos[r]);
// if (tmp2[0]+tmp2[1]!=cnt) id.insert(pos[r]), posr.pop_back();
// else{
// reverse(posr.begin(), posr.end());
// int cl=tmp2[0]-id.order_of_key(pos[r]);
// int cr=tmp2[1]-((int)id.size()-id.order_of_key(pos[r]));
// self(self, posl, cl);
// self(self, posr, cr);
// return;
// }
// }
}else{
int cl=tmp[0]-id.order_of_key(pos[mid]);
int cr=cc-cl;
self(self, posl, cl);
self(self, posr, cr);
}
};
solve(solve, st, cnt-(int)id.size());
for (int i:id){
auto tmp=Ask(i);
if (tmp[0]+tmp[1]==0) return i;
}
return -1;
}
