#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
//vector<int> ask(int i);
int find_best(int N) {
unordered_map<int, vector<int>> answers;
int oldN = N;
for(N = 1; N < oldN; N <<= 1);
function<vector<int>(int)> new_ask = [&](int i) {
if (i >= oldN) return new_ask(oldN-1);
if (!answers.count(i)) answers.insert({i, ask(i)});
return answers[i];
};
set<int> pos;
srand(time(NULL));
int quanti = 0;
for(int i = 0; i < 150; i++) {
auto schifooooo = new_ask(rand()%oldN);
quanti = max(quanti, schifooooo[0]+schifooooo[1]);
}
auto trova = [&](int fw, int tw, int f0) {
vector<int> f = {f0, 0};
int skip = 0, c = fw;
do {
if (!pos.count(c)) {
f = new_ask(c);
if (f[0]+f[1] != quanti) {
pos.insert(c); skip++;
}
} else skip++;
c--;
}while (f[0]+f[1] != quanti && c != tw);
if (skip == fw-tw) f = {f0, f0};
return f[0]+skip;
};
vector<int> values = {quanti};
for (int lev = N/2; lev > 0; lev = (lev)>>1) {
vector<int> nv;
int j = 0;
for (int i = lev-1; i < N; i+=lev) {
int td = nv.empty() ? 0 : nv.back();
int tt = j == 0 ? 0 : values[j-1];
if ((i/lev)%2 == 0) {
if (values[j]-tt == 0) nv.push_back(td);
else nv.push_back(trova(min(i, N-1), i-lev, tt));
}
else {
nv.push_back(values[j]);
j++;
}
}
swap(nv, values);
}
for (int i = values.size()-1; i > 0; i--) {
values[i] -= values[i-1];
}
for (int i = 0; i < N; i++) {
if (values[i] >= 1) pos.insert(i);
}
for (int x : pos) {
auto lll = new_ask(x);
if (lll[0]+lll[1] == 0) return x;
}
return -1;
}
#ifndef EVAL
static const int max_q = 10000;
static int n;
static int query_count = 0;
static vector<int> g;
static vector<vector<int> > rank_count;
int find_best(int n);
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;
}
#endif
