#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];
set<int>s;
int n;
/*vi ask(int ind){
vi a;
a.push_back(0),a.push_back(0);
for(int i=0;i<ind;i++) if(t[i]<t[ind]) a[0]++;
for(int i=ind+1;i<n;i++) if(t[i]<t[ind]) a[1]++;
return a;
}*/
int bs(int pocz,int kon,int x,int l,int r){
int sr;
while(pocz<=kon){
sr=(pocz+kon)/2;
vi a=ask(sr);
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{
if(a[1]>r) pocz=sr+1;
else return INT_MAX;
}
}
return INT_MAX;
}
int find_best(int m){
n=m;
int l=0,r=0;
int ind=0,p=sqrt(n);
int maxi=0;
if(p*p!=n) p++;
for(int i=0;i<=p;i++){
vi a=ask(i);
maxi=max(maxi,a[0]+a[1]);
t[i]=a[0]+a[1];
if(t[i]==0) return i;
}
while(ind<n-1){
s.insert(ind);
if(t[ind]==maxi) {p=t[ind];break;}
ind++,l++;
}
auto it=s.end();
it--;
s.insert(n);
while(*it!=n){
auto it2=it;
it2++;
int pom=bs(*it+1,*it2-1,p,l,r);
if(pom!=INT_MAX){
if(pom<0) return abs(pom)-1;
s.insert(pom);
r++;
}else{
l++,r--;
it++;
}
}
return 0;
}
/*int main(){
ios_base::sync_with_stdio(0),cin.tie(0);
int k;
cin>>k;
for(int i=0;i<k;i++) cin>>t[i];
cout<<find_best(k)<<"\n";
}*/
