#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;
using pii = pair<int, int>;
void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    vector<vector<int>> b(n + 1, vector<int>(n + 1, 0));
    vector<vector<int>> c(n + 1, vector<int>(n + 1, 0));
    vector<int> t;
    vector<int> cnt(2, 0);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        t.push_back(a[i]);
    }
    sort(t.begin(), t.end());
    t.erase(unique(t.begin(), t.end()), t.end());
    auto chk = [&](int x) -> bool
    {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                b[i][j] = c[i][j] = 0;

        for (int len = 1; len <= n; len++)
        {
            cnt[0] = cnt[1] = 0;
            for (int i = 1; i <= len; i++)
                cnt[(a[i] <= x)]++;
            b[1][len] = (cnt[1] >= (len + 1) / 2);
            for (int r = len + 1; r <= n; r++)
            {
                cnt[(a[r - len] <= x)]--;
                cnt[(a[r] <= x)]++;
                b[r - len + 1][r] = (cnt[1] >= (len + 1) / 2);
            }
        }
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
        auto qry = [&](int x1, int y1, int x2, int y2) -> int
        {
            return b[x2][y2] - b[x1 - 1][y2] - b[x2][y1 - 1] + b[x1 - 1][y1 - 1];
        };
        int tot = 0;
        for (int i = 1; i <= n; i++)
            for (int j = i; j <= n; j++)
            {
                int len = j - i + 1;
                int sum = (len * (1 + len)) / 2;
                c[i][j] = (qry(i, i, j, j) >= (sum + 1) / 2);
                tot += c[i][j];
            }
        int ins = (n * (n + 1)) / 2;
        return (tot >= (ins + 1) / 2);
    };
    int l = 0, r = (int)t.size() - 1;
    // for (auto &i : t)
    //     cout << i << " ";
    // cout << endl;
    // cout << chk(3) << endl;
    // cout << chk(4) << endl;
    // cout << chk(5) << endl;
    // cout << chk(8) << endl;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        //   cout << mid << " " << chk(t[mid]) << endl;
        if (chk(t[mid]))
            r = mid;
        else
            l = mid + 1;
    }
    // cout << l << endl;
    cout << t[l];
}
int main()
{
#ifdef x3ea
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int _ = 1;
    // cin >> _;
    for (int i = _; i >= 1; i--)
        solve();
    return 0;
}