#include <bits/stdc++.h>
#define C__ const
#define int long long
using namespace std;
C__ int N_ = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3fLL;
int n, m, a[N_], b[N_];
signed main() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) {
		priority_queue<pair<int, int> > que1;
		priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > que2;
		que1.push({-inf, 0}), que2.push({inf, 0});
		for (int j = i; j <= n; j++) {
			int x = a[j], y = j;
			if ((j - i) & 1) {
				if (x < que1.top().first) {
					que1.push({x, y});
					x = que1.top().first, y = que1.top().second;
					que1.pop();
				}
				que2.push({x, y});
			} else {
				if (x > que2.top().first) {
					que2.push({x, y});
					x = que2.top().first, y = que2.top().second;
					que2.pop();
				}
				que1.push({x, y});
			}
			++b[que1.top().second];
		}
	}
	vector<int> idx(n);
	iota(idx.begin(), idx.end(), 1);
	sort(idx.begin(), idx.end(), [&](int i, int j) { return a[i] < a[j]; } );
	for (int c = 0; c < (int) idx.size(); c++)
		if (c > 0) b[idx[c]] += b[idx[c - 1]];
	m = (b[idx[n - 1]] + 1) / 2;
	int l = 0, r = n - 1;
	while (l < r) {
		int mid = l + (r - l) / 2;
		if (b[idx[mid]] < m) l = mid + 1;
		else r = mid;
	}
	cout << a[idx[l]] << "\n";
	return 0;
}