#include <bits/stdc++.h>
//#pragma GCC optimize("O3,unroll-loops")
using namespace std;
#define f first
#include "prize.h"
#define ll long long
#define s second
/*
static const int max_q = 10000;cout
static int n;
static int query_count = 0;
static vector<int> g;
static vector<vector<int> > rank_count;*/
//vector<int> ask(int i);
/*
{
query_count++;
if(query_count > max_q) {
cerr << "Query limit exceeded" << endl;
exit(0);
}
if(i < 0 || i >= n) {
cerr << "Bad index: " << i << endl;
exit(0);
}
vector<int> res(2);
res[0] = rank_count[g[i] - 1][i + 1];
res[1] = rank_count[g[i] - 1][n] - res[0];
return res;
}*/
int haha;
vector<int>seg; int po=1;
void up(int pos){
pos+=po;
seg[pos]=1;
for (pos/2;pos>0;pos/=2) seg[pos]=seg[2*pos]+seg[2*pos+1];
}
int sum(int l, int r){
l+=po; r+=po;
if (l==r) return seg[l];
int su=seg[l]+seg[r];
while(r-l>1){
if (l%2==0) su+=seg[l+1];
if (r&1) su+=seg[r-1];
l/=2; r/=2;
}
return su;
}
int N;
vector<array<int,2>>check;
int find_best(int n) {
srand(time(NULL));
N=n;
check.resize(n+1,{-1,-1});
while (po<n) po<<=1;
seg.resize(2*po);
int p=0;
pair<int,int> mx={0,-1};
for (int i=0;i<200;i++){
vector<int>x=ask(((ll)(rand()%N)*(ll)(rand()%N)+i*i)%N);
mx=max(mx,{x[0]+x[1],12});
}
if (mx.f<sqrt(n)){
vector<int>y(475);
while (p<n&&p<475){
vector<int>q=ask(p);
check[p]={q[0],q[1]};
y[p]=q[0]+q[1];
if (y[p]==0) return p;
mx=max(mx,{y[p],p});
p++;
}
}
haha=mx.f;
vector<int>x=ask(0);
check[0]={x[0],x[1]};
if (x[0]+x[1]==0) return 0;
check[N]={42,0};
bool find=0;
auto search =[&](int l, int r,auto &&search)-> void {
if (l==r+1) return;
if (find) return;
int m=(l+r)/2;
vector<int>x=ask(m);
check[m]={x[0],x[1]};
int sus=x[0]+x[1];
if (sus==0) {find=1;return;}
if (sus==haha){
if (x[0]-check[l][0]) search(l,m,search);
if (x[1]-check[r][1]) search(m,r,search);
}
else{
int l1=m,r1=m;
if (x[0]+x[1]==0) {find=1;return;}
if (x[0]>0){while (check[l1][0]+check[l1][1]<haha){
l1--;
if (l1==l) return;
vector<int>y=ask(l1);
check[l1]={y[0],y[1]};
if (y[0]+y[1]==0) {find=1;return;}
}
if (find) return;
if (check[l1][0]-check[l][0]) search(l,l1,search);}
if (x[1]>0){while (check[r1][0]+check[r1][1]<haha){
r1++;
if (r1==r) return;
vector<int>y=ask(r1);
check[r1]={y[0],y[1]};
if (y[0]+y[1]==0) {find=1;return;}
}
if (find) return;
if (check[r1][1]-check[r][1]) search(r1,r,search);}
}
if (find) return;
};
search(0,N,search);
int found;
for (int i=0;i<N;i++){
if (check[i][0]+check[i][1]==0) found=i;
}
return found;
}
/*#ifdef EVAL
int main() {
freopen("output.txt","r",stdin);
cin >> n;
g.resize(n);
for(int i = 0; i < n; i++) {
cin >> g[i];
if(g[i] < 1) {
cerr << "Invalid rank " << g[i] << " at index " << i << endl;
exit(0);
}
}
int max_rank = *max_element(g.begin(), g.end());
rank_count.resize(max_rank + 1, vector<int>(n + 1, 0));
for(int r = 0; r <= max_rank; r++) {
for(int i = 1; i <= n; i++) {
rank_count[r][i] = rank_count[r][i - 1];
if(g[i - 1] == r)
rank_count[r][i]++;
}
}
for(int i = 0; i <= n; i++)
for(int r = 1; r <= max_rank; r++)
rank_count[r][i] += rank_count[r - 1][i];
int res = find_best(n);
cout << res << endl << "Query count: " << query_count << endl;
return 0;
}
#endif//*/
