#include <bits/stdc++.h> using namespace std; using ll = long long; using vi = vector<int>; vi ask(int i); namespace k1r1t0 { const int N = 210000; const int G = 476; map<int, vi> ans; vi check(int i) { if (ans.find(i) == ans.end()) ans[i] = ask(i); return ans[i]; } int solve(vi &cur, int cl, int cr, int val) { if (cl + cr == val) return -1; int len = cur.size(); if (len == 1) { vi f = check(cur[0]); if (f[0] + f[1] == 0) return cur[0]; return -1; } int l = len / 2, r = len / 2; bool f = true; int here = val - cl - cr; while (true) { if (here == 0 || l == -1 || r == len) return -1; if (f) { // check r vi f = check(cur[r]); if (f[0] + f[1] == val) { vi vl, vr; for (int i = 0; i < l; i++) vl.push_back(cur[i]); for (int i = r + 1; i < len; i++) vr.push_back(cur[i]); int v1 = solve(vl, cl, f[1] + r - l, val); if (v1 != -1) return v1; int v2 = solve(vr, f[0], cr, val); return v2; } else { here--; if (f[0] + f[1] == 0) return cur[r]; } l--; } else { // check l vi f = check(cur[l]); if (f[0] + f[1] == val) { vi vl, vr; for (int i = 0; i < l; i++) vl.push_back(cur[i]); for (int i = r + 1; i < len; i++) vr.push_back(cur[i]); int v1 = solve(vl, cl, f[1], val); if (v1 != -1) return v1; int v2 = solve(vr, f[0] + r - l, cr, val); return v2; } else { here--; if (f[0] + f[1] == 0) return cur[l]; } r++; } f = !f; } } int find_best(int n) { int val = 0; for (int i = 0; i < min(n, G + 1); i++) { vi f = check(i); if (f[0] + f[1] == 0) return i; val = max(val, f[0] + f[1]); if (val >= 450) break; } vi cur; for (int i = 0; i < n; i++) cur.push_back(i); return solve(cur, 0, 0, val); } }; int find_best(int n) { return k1r1t0::find_best(n); } #ifdef LOCAL typedef std::vector<int> ints; static ints xs; static int n, cnt; std::vector<int> ask (int i) { assert((0 <= i) && (i < n)); ints result(2, 0); for (int j = 0; j < n; j++) if (xs[i] > xs[j]) result[(j > i ? 1 : 0)]++; cnt++; return result; } int main (int argc, char **argv) { assert(scanf("%d", &n) == 1); xs.resize(n); for (int i = 0; i < n; i++) assert(scanf("%d", &xs[i]) == 1); int result = find_best(n); printf("%d %d\n", result, cnt); } #endif