#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mll map<ll, ll>
#define mii map<int, int>
#define vll vector<ll>
#define vi vector<int>
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define lowbit(x) (x & (-x))
#define endl '\n'
const ll N = 1e5;
const ll M = 500 + 10;
const ll mod = 998244353;
const ll inf = 1e17;
const double eps = 1e-6;
int dx[10] = {1, 1, -1, -1, -1, -1, 1, 1, 0}, dy[10] = {1, -1, 1, -1, 1, -1, 1, -1, 0}; // 0左 1右 2下 3上
struct Segment
{
    Segment(ll n)
    {
        seg.resize((n + 10) << 2);
        cn1.resize(n + 10);
    }

    struct info
    {
        ll sum;
        info() {}
        info(ll a) : sum(a) {}
    };

    struct tag
    {
        ll t1;
    };

    struct sb
    {
        info val;
        tag t;
        ll sz;
    };

    info info_merge(info l, info r) // 信息结合函数
    {
        info a;
        a.sum = l.sum + r.sum;
        return a;
    }

    info i_tmerge(info v, tag t) // 标记作用函数
    {
        info a;
        a = v;
        a.sum += t.t1;
        return a;
    }

    tag tag_merge(tag l, tag r) // 标记结合函数
    {
        tag t;
        t.t1 = l.t1 + r.t1;
        return t;
    }

    vector<sb> seg;
    vector<ll> cn1;

    void update(ll id) // 向上更新
    {
        seg[id].val = info_merge(seg[id * 2].val, seg[id * 2 + 1].val);
    }

    void settag(ll id, tag t) // 设置懒标记
    {
        seg[id].t = tag_merge(seg[id].t, t);
        t.t1 *= seg[id].sz;
        seg[id].val = i_tmerge(seg[id].val, t);
    }

    void pushdown(ll id) // 下传懒标记
    {
        if (!seg[id].t.t1)
        {
            return;
        }
        settag(id * 2, seg[id].t);
        settag(id * 2 + 1, seg[id].t);
        seg[id].t = {0};
    }

    void build(ll id, ll l, ll r) // 建树
    {
        seg[id].sz = r - l + 1;
        if (l == r)
        {
            seg[id].val = info(0);
        }
        else
        {
            ll mid = (l + r) >> 1;
            build(id * 2, l, mid);
            build(id * 2 + 1, mid + 1, r);
            update(id);
        }
    }

    void change(ll id, ll l, ll r, ll pos, tag val) // 单改
    {
        if (l == r)
        {
            seg[id].val = i_tmerge(seg[id].val, val);
        }
        else
        {
            pushdown(id);
            ll mid = (l + r) >> 1;
            if (pos <= mid)
                change(id * 2, l, mid, pos, val);
            else
                change(id * 2 + 1, mid + 1, r, pos, val);
            update(id);
        }
    }

    void modify(ll id, ll l, ll r, ll ql, ll qr, tag t) // 区改
    {
        if (l >= ql && r <= qr)
        {
            settag(id, t);
            return;
        }
        ll mid = (l + r) >> 1;
        pushdown(id);
        if (qr <= mid)
            modify(id * 2, l, mid, ql, qr, t);
        else if (ql > mid)
            modify(id * 2 + 1, mid + 1, r, ql, qr, t);
        else
        {
            modify(id * 2, l, mid, ql, mid, t);
            modify(id * 2 + 1, mid + 1, r, mid + 1, qr, t);
        }
        update(id);
    }

    info query(ll id, ll l, ll r, ll ql, ll qr) // 区查
    {
        // assert(ql > qr);
        if (l >= ql && r <= qr)
        {
            return seg[id].val;
        }
        ll mid = (l + r) >> 1;
        pushdown(id);
        if (qr <= mid)
            return query(id * 2, l, mid, ql, qr);
        else if (ql > mid)
            return query(id * 2 + 1, mid + 1, r, ql, qr);
        else
            return info_merge(query(id * 2, l, mid, ql, mid), query(id * 2 + 1, mid + 1, r, mid + 1, qr));
    }

    info check(ll id, ll l, ll r, ll pos) // 单查
    {
        if (l == r && l == pos)
        {
            return seg[id].val;
        }
        ll mid = (l + r) >> 1;
        pushdown(id);
        if (pos <= mid)
            return check(id * 2, l, mid, pos);
        else
            return check(id * 2 + 1, mid + 1, r, pos);
    }

    ll bs(ll id, ll l, ll r, ll x) // 二分
    {
        if (l == r)
        {
            return l;
        }
        ll mid = (l + r) >> 1;
        if (seg[id * 2].val.sum >= x)
            return bs(id * 2, l, mid, x);
        else
            return bs(id * 2 + 1, mid + 1, r, x - seg[id * 2].val.sum);
    }
};

void solve()
{
    ll n;
    cin >> n;
    vll cn(n + 1);
    vll rk;
    for (int i = 1; i <= n; i++)
    {
        cin >> cn[i];
        rk.push_back(cn[i]);
    }
    sort(rk.begin(), rk.end());
    rk.erase(unique(rk.begin(), rk.end()), rk.end());
    ll m = rk.size() + 1;
    vector<vll> b(n + 1, vll(n + 1));
    Segment tr(rk.size() + 1);
    for (int i = 1; i <= n; i++)
    {
        for (int j = i; j <= n; j++)
        {
            ll s = lower_bound(rk.begin(), rk.end(), cn[j]) - rk.begin() + 1;
            tr.change(1, 1, m, s, {1});
            b[i][j] = rk[tr.bs(1, 1, m, (j - i + 2) / 2) - 1];
        }
        tr.build(1, 1, m);
    }
    ll l = 1, r = 1e9;
    function<bool(ll)> check = [&](ll mid)
    {
        vector<vll> pre(n + 1, vll(n + 1));
        for (int i = 1; i <= n; i++)
        {
            for (int j = i; j <= n; j++)
            {
                if (b[i][j] <= mid)
                {
                    pre[i][j] = 1;
                }
            }
        }
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                pre[i][j] += pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1];
            }
        }
        ll cnt = 0;
        for (int i = 1; i <= n; i++)
        {
            for (int j = i; j <= n; j++)
            {
                ll sum = pre[j][j] - pre[i - 1][j] - pre[j][i - 1] + pre[i - 1][i - 1];
                ll len = j - i + 1;
                if (sum >= (len * (len + 1) / 2 + 1) / 2)
                {
                    cnt++;
                }
            }
        }
        return cnt >= (n * (n + 1) / 2 + 1) / 2;
    };
    while (l < r)
    {
        ll mid = (l + r) >> 1;
        if (check(mid))
        {
            r = mid;
        }
        else
        {
            l = mid + 1;
        }
    }
    cout << r << endl;
}
int main()
{
    IOS;
    ll t = 1;
    // cin >> t;
    for (int i = 1; i <= t; i++)
    {
        solve();
    }
    return 0;
}
/*
 */