#ifdef t9unkubj
#include"debug.cpp"
//#include"template_no_debug.h"
#else
#include"prize.h"
#define dbg(...) 199958
#endif
#undef _GLIBCXX_DEBUG
#pragma GCC optimize("O3")
using namespace std;
#include<bits/stdc++.h>
using ll=long long;
using ull=unsigned long long;
template<class T>using vc=vector<T>;
template<class T>using vvc=vc<vc<T>>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++)
#define DREP(i,n,m) for(ll i=(n);i>=(m);i--)
#define drep(i,n) for(ll i=((n)-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template<class T,class F>
bool chmin(T &x, F y){
if(x>y){
x=y;
return true;
}
return false;
}
template<class T, class F>
bool chmax(T &x, F y){
if(x<y){
x=y;
return true;
}
return false;
}
int find_best(int n);
namespace judge{
static const int max_q = 10000;
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;
}
void run(int n_,vc<int>a){
n=n_;
g=a;
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];
assert(a[find_best(n)]==1);
cout << "Query count: " << query_count << endl;
return ;
}
};
#ifdef t9unkubj
using namespace judge;
#endif
/*
二分探索
"上"の階層のものがわかるので頑張る
*/
vc<int> Ask(int x){
static map<int,vc<int>>memo;
if(memo.count(x))return memo[x];
return memo[x]=ask(x);
}
int find_best(int n) {
{
map<int,set<pair<int,int>>>le,ri;
queue<pair<int,int>>now_que,nxt_que;
vc<array<int,4>>update;
int mid=n>>1;
auto res=Ask(mid);
int K=res[0]+res[1];
le[K].insert({mid,res[0]}),
ri[K].insert({mid,res[1]});
now_que.push({0,n});
while(1){
if(now_que.size()){
auto [l,r]=now_que.front();now_que.pop();
if(l==r)continue;
if(l+1==r){
if(Ask(l)[0]+Ask(l)[1]==0)
return l;
continue;
}
int mid=l+r>>1;
auto res=Ask(mid);
int K=res[0]+res[1];
int r0=res[0],r1=res[1];
{
auto it=le[K].lower_bound({mid,-1});
if(it!=le[K].begin())r0-=prev(it)->second;
}
{
auto it=ri[K].lower_bound({mid+1,-1});
if(it!=ri[K].end())r1-=it->second;
}
if(res[0]+res[1]==0){
return mid;
}
if(r0){
if(mid-l>1){
int nxt_mid=mid+l>>1;
auto R=Ask(nxt_mid);
update.push_back({R[0]+R[1],nxt_mid,R[0],R[1]});
}
nxt_que.push({l,mid});
}
if(r1){
if(r-(mid+1)>1){
int nxt_mid=(mid+1+r)>>1;
auto R=Ask(nxt_mid);
update.push_back({R[0]+R[1],nxt_mid,R[0],R[1]});
}
nxt_que.push({mid+1,r});
}
}else if(nxt_que.size()){
now_que=move(nxt_que);
for(auto&[to,x,y,z]:update)
le[to].insert({x,y}),ri[to].insert({x,z});
update.clear();
}else break;
}
}
}
vc<int>make(int n){
vc<int>ap{1};
while(1){
ll r=ap.back();
if(r*r+1+accumulate(all(ap),0)>n){
ap.back()+=n-accumulate(all(ap),0);
vc<int>is;
rep(i,ap.size())rep(j,ap[i])is.push_back(i+1);
return is;
}
ap.push_back(r*r+1);
}
std::chrono::steady_clock().now().time_since_epoch().count();
}
#ifdef t9unkubj
void run1(){
mt19937 mt(4);
int n=2e5;
auto a=make(n);
shuffle(all(a),mt);
dbg(a.size());
run(n,a);
dbg("OKOK"s);
}
void run2(){
int n;
cin>>n;
vc<int>a(n);
rep(i,n)cin>>a[i];
run(n,a);
}
int main(){run1();}
#endif
/*
8
3 2 3 1 3 3 2 3
*/
