#include "prize.h"
#include <bits/stdc++.h>
#define MIN -1
#define MAX 1000000000
#define all(a) a.begin (), a.end ()
#define mp make_pair
#define pb push_back
using namespace std;
typedef vector <int> vi;
typedef long long int ll;
typedef pair <int, int> ii;
pair<int, int> v[201000];
bool aux[200100];
pair<int, int> visitado(int pos){
if (aux[pos]){
return v[pos];
}
aux[pos] = 1;
vector <int> v1 = ask(pos);
return v[pos] = {v1[0], v1[1]};
}
int find_best(int n) {
int mx = MIN;
int mxpos = 0;
for (int i = 0; i < min(474, n); i++){
pair<int, int> v = visitado(i);
if (v.first+v.second == 0)
return i;
if (v.first + v.second > mx){
mx = v.first + v.second;
mxpos = i;
}
}
int aux1 = mxpos;
while(1){
int l = aux1+1, r = n;
while(l < r){
int mid = (l+r)/2;
pair<int, int> v = visitado(mid);
if (v.first+v.second == 0)return mid;
if (v != visitado(aux1))
r = mid; else
l = mid+1;
}
aux1 = l;
while(aux1 < n){
if (visitado(aux1).first + visitado(aux1).second == visitado(mxpos).first+visitado(mxpos).second)
break;
if (visitado(aux1).first + visitado(aux1).second == 0)
return aux1;
aux1++;
}
}
}
/*
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;
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;
}
*/
