#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
int query;
#ifdef tabr
function<vector<int>(int)> ask;
#else
#include "prize.h"
#endif
int find_best(int n) {
if (n <= 5000) {
for (int i = 0; i < n; i++) {
auto a = ask(i);
if (a[0] + a[1] == 0) {
return i;
}
}
assert(false);
}
vector<vector<int>> res(n);
int B = (int) sqrt(n) - 20;
set<int> st;
for (int i = 0; i <= n; i++) {
st.emplace(i);
}
auto Ask = [&](int i) {
if (!res[i].empty()) {
return res[i][0] + res[i][1];
}
assert(query <= 10000);
query++;
st.erase(i);
res[i] = ask(i);
return res[i][0] + res[i][1];
};
vector<int> sz(B + 1);
for (int i = 0; i < B; i++) {
sz[i + 1] = sz[i] + (n + i) / B;
}
int mx = -1;
for (int i = 0; i < B; i++) {
mx = max(mx, Ask(sz[i]));
}
for (int i = 0; i < B; i++) {
if (Ask(sz[i]) == mx) {
continue;
}
for (int j = sz[i] + 1; j < sz[i + 1]; j++) {
if (Ask(j) == mx) {
break;
}
}
}
for (int i = 0; i < n; i++) {
if (!res[i].empty() && Ask(i) == 0) {
return i;
}
}
function<void(int, int, int)> solve = [&](int low, int high, int cnt) {
if (cnt == 0 || low == high) {
return;
}
assert(cnt > 0);
assert(cnt <= high - low);
assert(Ask(low - 1) == mx);
int mid = (high + low) >> 1;
for (int i = mid; i < high; i++) {
if (Ask(i) == mx) {
int c = res[i][0] - res[low - 1][0] - (i - mid);
solve(low, mid, c);
solve(i + 1, high, cnt - c);
return;
}
cnt--;
}
solve(low, mid, cnt);
};
for (int k = 0; k < B; k++) {
int low = *st.lower_bound(sz[k]) - 1;
int high = *st.lower_bound(sz[k + 1]) - 1;
int cnt = 0;
assert(low < high);
if (k == B - 1) {
cnt = mx;
for (int i = 0; i < sz[k]; i++) {
if (!res[i].empty() && Ask(i) < mx) {
cnt--;
}
}
} else {
cnt = res[high][0] - res[low][0] - (high - sz[k + 1]);
}
low++;
high = sz[k + 1];
debug(k, low, high, cnt);
solve(low, high, cnt);
for (int i = sz[k]; i < sz[k + 1]; i++) {
if (!res[i].empty() && Ask(i) == 0) {
return i;
}
}
}
assert(false);
return -1;
}
#ifdef tabr
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int k;
cin >> k;
vector<int> c(k);
for (int i = 0; i < k; i++) {
cin >> c[i];
}
int n = accumulate(c.begin(), c.end(), 0);
vector<int> p;
for (int i = 0; i < k; i++) {
for (int j = 0; j < c[i]; j++) {
p.emplace_back(i);
}
}
mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
shuffle(p.begin(), p.end(), rng);
ask = [&](int i) {
vector<int> res(2);
for (int j = 0; j < i; j++) {
if (p[j] < p[i]) {
res[0]++;
}
}
for (int j = i + 1; j < n; j++) {
if (p[j] < p[i]) {
res[1]++;
}
}
return res;
};
// debug(p);
int id = find_best(n);
debug(id);
debug(query);
assert(p[id] == 0);
return 0;
}
#endif
