#include <bits/stdc++.h> #include "prize.h" using namespace std; //vector<int> ask(int i); int find_best(int N) { unordered_map<int, vector<int>> answers; int oldN = N; for(N = 1; N < oldN; N <<= 1); function<vector<int>(int)> new_ask = [&](int i) { if (i >= oldN) return new_ask(oldN-1); if (!answers.count(i)) answers.insert({i, ask(i)}); return answers[i]; }; set<int> pos; srand(time(NULL)); int quanti = 0; for(int i = 0; i < 150; i++) { auto schifooooo = new_ask(rand()%oldN); quanti = max(quanti, schifooooo[0]+schifooooo[1]); } auto trova = [&](int fw, int tw, int f0) { vector<int> f = {f0, 0}; int skip = 0, c = fw; do { if (!pos.count(c)) { f = new_ask(c); if (f[0]+f[1] != quanti) { pos.insert(c); skip++; } } else skip++; c--; }while (f[0]+f[1] != quanti && c != tw); if (skip == fw-tw) f = {f0, f0}; return f[0]+skip; }; vector<int> values = {quanti}; for (int lev = N/2; lev > 0; lev = (lev)>>1) { vector<int> nv; int j = 0; for (int i = lev-1; i < N; i+=lev) { int td = nv.empty() ? 0 : nv.back(); int tt = j == 0 ? 0 : values[j-1]; if ((i/lev)%2 == 0) { if (values[j]-tt == 0) nv.push_back(td); else nv.push_back(trova(min(i, N-1), i-lev, tt)); } else { nv.push_back(values[j]); j++; } } swap(nv, values); } for (int i = values.size()-1; i > 0; i--) { values[i] -= values[i-1]; } for (int i = 0; i < N; i++) { if (values[i] >= 1) pos.insert(i); } for (int x : pos) { auto lll = new_ask(x); if (lll[0]+lll[1] == 0) return x; } return -1; } #ifndef EVAL static const int max_q = 10000; static int n; static int query_count = 0; static vector<int> g; static vector<vector<int> > rank_count; int find_best(int n); 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; } #endif