//#include "prize.h"
#include<bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#define sz(v) (int)v.size()
#define fi first
#define se second
using namespace std;
static const int max_q = 10000;
static int n;
static int query_count = 0;
static vector<int> g;
static vector<vector<int> > rank_count;
//#include "prize.h"
vector<int>ask(int);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rr(int l, int r){
return(uniform_int_distribution<int>(l, r)(rng));
}
int N = 2e5 + 5;
int MX = 0;
vector<pair<int, int>>special;
vector<int>memo[200005];
set<int>unvisited;
int Q = 10000;
int bit[200005 + 1];
void upd(int p, int v){
while(p <= N){
bit[p] += v; p += p & (-p);
}
}
int gett(int p){
int ans = 0;
while(p){
ans += bit[p]; p -= p & (-p);
}
return(ans);
}
int kth(int x){
int pos = 0, sm = 0;
for(int i = 17; i >= 0; i--){
if(pos + (1 << i) <= N && bit[pos + (1 << i)] + sm < x){
pos += (1 << i); sm += bit[pos];
}
}
return(pos + 1);
}
pair<vector<int>, bool>get(int x){
if(sz(memo[x]) == 2)return(make_pair(memo[x], 0));
Q--;
memo[x] = ask(x);
if(memo[x][0] + memo[x][1] < MX){
special.push_back(make_pair(x, memo[x][0] + memo[x][1]));
return(make_pair(memo[x], 1));
}
return(make_pair(memo[x], 0));
}
int find_best(int n) {
N = n;
int pos, L = 1, R = n, cntzero = 0, cntone = 0;
for(int i = 0; i < n; i++){
upd(i + 1, 1);
}
for(int i = 0; i < 200; i++){
int cand = rr(0, n - 1); get(cand);
MX = max(MX, memo[cand][0] + memo[cand][1]);
memo[cand].clear();
}
special.clear();
while(Q){
//assert(L <= R);
int mid = (L + R) >> 1;
//cerr << mid << "\n";
pos = kth(mid) - 1;
assert(sz(memo[pos]) == 0);
upd(pos + 1, -1);
//assert(pos >= L && pos <= R);
auto [cnt, isspecial] = get(pos);
if(cnt[0] + cnt[1] == 0)return(pos);
int rnk = cnt[0] + cnt[1];
for(auto i: special){
if(i.se < rnk){
if(i.fi < pos){
cnt[0]--;
}else if(i.fi > pos){
cnt[1]--;
}
}
}
//assert(cnt[0] >= 0 && cnt[1] >= 0);
//assert(isspecial || (cnt[0] >= cntzero && cnt[1] >= cntone));
cnt[0] -= cntzero; cnt[1] -= cntone;
if(cnt[0] > cnt[1]){
R = mid - 1;
cntone += cnt[1];
}else{
L = mid; R--;
cntzero += cnt[0];
}
if(isspecial){
L = 1; R = gett(n); cntzero = cntone = 0;
}
//assert(cnt[0] || cnt[1]);
}
//assert(0);
return(1);
}
/*
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 main() {
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;
}
*/
