#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*/