#include <bits/stdc++.h>
using namespace std;
vector<int> ask(int i);
vector<int> tutti_non_brutti;
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(m);
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, d);
}
rec(l, m, dentro, quanti_sx, quanti_dx);
}
int find_best(int N) {
int quanti = 0;
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;
}
if (s + d == 0) return i;
}
quanti_non_brutti = quanti;
rec(0, N, quanti, 0, 0);
return sol;
}
/*#ifdef EVAL
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*/
