#include<bits/stdc++.h>
using namespace std;
const int mn=3e5+5;
int n,a[mn];
priority_queue<int> q1;
priority_queue<int,vector<int>,greater<int> > q2;
map<int,int> mp;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    // q2.push(1);
    // q2.push(2);
    // cerr<<q2.top();
    for(int k=1;k<=n;k++)
    {
        while(!q1.empty())q1.pop();
        while(!q2.empty())q2.pop();
        for(int i=k;i<=n;i++)
        {
            q1.push(a[i]);
            if(q1.size()>q2.size()+1)
            {
                q2.push(q1.top());
                q1.pop();
                // q1.push(q2.top());
                // q2.pop();
            }
            while(!q2.empty() && q1.top()>q2.top())
            {
                q2.push(q1.top());
                q1.pop();
                q1.push(q2.top());
                q2.pop();
            }
            mp[q1.top()]++;
        }
    }
    int tmp=(n*(n+1)/2+1)/2;
    for(auto i:mp)
    {
        tmp-=i.second;
        if(tmp<=0)
        {
            printf("%d",i.first);
            return 0;
        }
    }
    // cerr<<"fin";
}