#include<bits/stdc++.h>
#include "prize.h"
#define fi first
#define se second
using namespace std;
typedef unsigned long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=2e5+10;
int t[N];
int t2[N][2];
set<int>s;
int n,ile;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vi que(int a){
if(t2[a][0]){
vi akt;
akt.push_back(t2[a][0]),akt.push_back(t2[a][1]);
return akt;
}
vi akt=ask(a);
t2[a][0]=akt[0],t2[a][1]=akt[1];
return akt;
}
int bs(int pocz,int kon,int x,int l){
int sr;
while(pocz<=kon){
sr=(pocz+kon)/2;
vi a=que(sr);
ile++;
if(a[0]+a[1]==0) return -(sr+1);
if(a[0]+a[1]!=x) return sr;
if(a[0]>l) kon=sr-1;
else pocz=sr+1;
}
return INT_MAX;
}
int find_best(int m){
n=m;
int l=0,p=0;
for(int i=1;i<=50;i++){
int a=uniform_int_distribution<int>(0,n-1)(rng);
vi akt=que(a);
p=max(p,akt[0]+akt[1]);
}
s.insert(-1);
auto it=s.begin();
s.insert(n);
while(*it!=n){
auto it2=it;
it2++;
ile=0;
if(*it+1==*it2){
l++,it++;
continue;
}
int k=*it2-1;
vi akt=que(k);
while(k>=*it+1 and akt[0]+akt[1]!=p){
if(akt[0]+akt[1]==0) return k;
s.insert(k),k--,akt=que(k);
}
if(k>=*it+1){
vi akt=que(k);
if(akt[0]+akt[1]==0) return k;
if(akt[0]==l){
l++,it++;
continue;
}
}else {l++,it++;continue;}
int pom=bs(*it+1,k,p,l);
if(pom!=INT_MAX){
if(pom<0) return abs(pom)-1;
s.insert(pom);
}
}
return 0;
}
