#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
