#include <iostream>
#include <vector>
#include <algorithm>
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);
// 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 quanti_non_brutti;
int sol = -1;
void rec(int l, int r, int dentro, int quanti_sx, int quanti_dx) {
if (r - l == 0) return;
if (dentro == 0) return;
int m = (l + r) / 2;
for (int k = m; k < r; k ++) {
auto v = ask(k);
int s = v[0], d = v[1];
if (s + d == 0) {
sol = k;
return;
}
if (s + d != quanti_non_brutti) {
continue;
}
s -= quanti_sx;
d -= quanti_dx;
rec(l, m, s, quanti_sx, quanti_dx + d);
rec(k + 1, r, d, s + quanti_sx, quanti_dx);
}
rec(l, m, dentro, quanti_sx, quanti_dx);
}
int find_best(int N) {
int quanti = 0;
int ziopera;
for (int i = 0; i < 500; i ++) {
auto v = ask(i);
int s = v[0], d = v[1];
if (s + d > quanti) {
quanti = s + d;
ziopera = i;
}
if (s + d == 0) return i;
}
quanti_non_brutti = quanti;
// cout << "quanti_non_brutti : " << quanti_non_brutti << '\n';
// cout << "primo lombrico : " << ziopera << '\n';
rec(0, N, quanti, 0, 0);
return sol;
}
// 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;
// }
