#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2e5+10;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int bit[MAXN];
void add(int pos, int x, int n){ for(;pos<=n;pos+=(pos&-pos)) bit[pos]+=x; }
int get(int pos){
int ret=0;
for(;pos>0;pos-=(pos&-pos)) ret+=bit[pos];
return ret;
}
pii memo[MAXN];
pii query(int x){
if(memo[x].fi!=-1) return memo[x];
vector<int> temp=ask(x);
return memo[x]={temp[0], temp[1]};
}
int mark[MAXN], tot;
int getNext(int l, int r, int comp, int n){
if(r<l) return -1;
int curr=(l+r)>>1;
pii at=query(curr);
if(!mark[curr] && at.fi+at.se<comp){
mark[curr]=1;
add(curr+1, 1, n);
return curr;
}
if(at.fi+at.se==comp){
if(at.se>get(n)-get(curr+1)) return getNext(curr+1, r, comp, n);
return getNext(l, curr-1, comp, n);
}
int temp=getNext(curr+1, r, comp, n);
if(temp!=-1) return temp;
return getNext(l, curr-1, comp, n);
}
int find_best(int n){
for(int i=0;i<n;i++) memo[i]={-1, -1};
int ver=-1, val=-1;
for(int i=0;i<8;i++){
int curr=rng()%n;
pii at=query(curr);
if(at.fi+at.se>val){
val=at.fi+at.se;
ver=curr;
}
}
for(int i=0;i<query(ver).se;i++){
int curr=getNext(ver+1, n-1, val, n);
tot++;
if(curr==-1) break;
pii aux=query(curr);
if(aux.fi+aux.se==0)
return curr;
}
tot=query(ver).se;
for(int i=0;i<query(ver).fi;i++){
int curr=getNext(0, ver-1, val, n);
tot++;
if(curr==-1) break;
pii aux=query(curr);
if(aux.fi+aux.se==0)
return curr;
}
return -1;
}
