#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_esterni, int quanti_dx_esterni) {
// 1. Condizioni di terminazione
if (sol != -1 || l >= r) return;
if (dentro == 0) return;
// 2. Caso Base: segmento di un solo elemento
if (r - l == 1) {
sol = l;
return;
}
// 3. Query singola (Ricerca Binaria)
int m = l + (r - l) / 2;
auto v = ask(m);
int s_assoluto = v[0]; // Premi più costosi a sinistra di m
int d_assoluto = v[1]; // Premi più costosi a destra di m
// 4. Diamante Trovato
if (s_assoluto + d_assoluto == 0) {
sol = m;
return;
}
// 5. Normalizzazione: calcola i conteggi 'dentro' il segmento
int s_dentro = s_assoluto - quanti_sx_esterni;
int d_dentro = d_assoluto - quanti_dx_esterni;
// Controlliamo se 'm' è un premio di riferimento (es. lecca-lecca)
if (s_assoluto + d_assoluto == quanti_non_brutti) {
// Se 'm' è un lecca-lecca, usiamo i suoi conteggi per restringere la ricerca.
// I premi più costosi sono quelli a sinistra (s_dentro) e a destra (d_dentro) di 'm'.
// Ricerca nel segmento sinistro: [l, m)
rec(l, m, s_dentro, quanti_sx_esterni, quanti_dx_esterni + d_dentro);
// Ricerca nel segmento destro: [m + 1, r)
rec(m + 1, r, d_dentro, quanti_sx_esterni + s_dentro, quanti_dx_esterni);
} else {
// Se 'm' NON è un lecca-lecca (è un premio più costoso),
// la soluzione deve trovarsi in uno dei due segmenti.
// La logica standard IOI è: il diamante non si può trovare dove ci sono
// già stati trovati premi più costosi di 'm'.
// Qui, per semplicità, si cerca il diamante che ha s+d=0.
// La logica del problema suggerisce di dividere semplicemente l'intervallo
// in base al conteggio 'dentro' (il numero di premi più costosi).
// Se s_dentro > 0, il segmento sinistro contiene ancora un premio costoso.
if (s_dentro > 0) {
rec(l, m, s_dentro, quanti_sx_esterni, quanti_dx_esterni + d_dentro);
}
// Se d_dentro > 0, il segmento destro contiene ancora un premio costoso.
if (d_dentro > 0) {
rec(m + 1, r, d_dentro, quanti_sx_esterni + s_dentro, quanti_dx_esterni);
}
}
}
int find_best(int N) {
// Il codice di pre-ricerca è ragionevole, ma:
// 1. Usa 473 (che è un numero specifico). Lo standard IOI usa 474 o 500.
// Lasciamo 473, ma in un contesto reale andrebbe adattato.
// 2. 'quanti_uguali' è un conteggio dei lecca-lecca tra 0 e 472.
int quanti = 0; // Il massimo s+d trovato (corrisponde al lecca-lecca)
int quanti_uguali = 0; // Numero di lecca-lecca trovati tra 0 e 472
int ziopera = -1; // Indice del primo lecca-lecca (non usato direttamente, ma utile)
for (int i = 0; i < 473; i ++) {
auto v = ask(i);
int s = v[0], d = v[1];
if (s + d > quanti) {
quanti = s + d;
ziopera = i;
quanti_uguali = 1; // Un nuovo massimo, resetta il conteggio a 1
} else if (s + d == quanti) {
quanti_uguali ++; // Trovato un altro premio di riferimento
}
if (s + d == 0) return i; // Trovato subito il diamante
}
quanti_non_brutti = quanti;
// Richiama la ricorsione solo sull'intervallo [473, N).
// quanti: il numero totale di premi costosi ancora "dentro" l'intervallo totale.
// quanti_uguali: il numero di lecca-lecca trovati nel segmento esterno [0, 472].
// L'algoritmo IOI corretto usa quanti_uguali come conteggio dei premi più costosi (non-lecca-lecca).
// Qui si assume che i parametri siano: (l, r, premi_costosi_dentro, premi_costosi_sx_esterni, premi_costosi_dx_esterni)
// Assumendo che 'quanti' sia il numero totale di premi costosi (non-lecca-lecca) in tutta la riga N,
// e che i lecca-lecca non siano mai contati:
// Dentro: quanti (tutti i non-lecca-lecca non ancora trovati) - (premi costosi trovati in [0, 472])
// Premi costosi trovati in [0, 472] = 473 - quanti_uguali
int premi_costosi_in_esterni = (473 - quanti_uguali);
int dentro_segmento_iniziale = quanti - premi_costosi_in_esterni;
rec(473, N, dentro_segmento_iniziale, premi_costosi_in_esterni, 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;
// }
