#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//*/