#include<bits/stdc++.h>
#define int long long 
#define endl "\n"
#define x first
#define y second
#define de(a) #a << " = " << (a)
#define all(x) x.begin(),x.end()
using namespace std;
typedef pair<int,int> PII;
const int N=2e3+10,mod=1e9+7,inf=0x3f3f3f3f3f3f3f3f,P=131;
const double eps=1e-8,pi=acos(-1.0);
int s[N][N],b[N][N];
void solve(int T)
{
	int n;
	cin>>n;
	vector<int>a(n+1);
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int len=1;len<=n;len++)
	{
		multiset<int>q2;
		multiset<int,greater<int>>q1;
		int mid=(len+1)/2;
		for(int r=1,l=1;r<=n;r++)
		{
			if(q1.size()<mid)q1.insert(a[r]);
			else
			{
				if(q1.size())
				{
					if(*(q1.begin())<a[r])q2.insert(a[r]);
					else
					{
						q2.insert(*(q1.begin()));
						q1.erase(q1.begin());
						q1.insert(a[r]);
					}
				}
				else q2.insert(a[r]);
			}
			if(r-l+1==len)
			{
				b[l][r]=*(q1.begin());
				if(q1.count(a[l]))
				{
					q1.erase(q1.find(a[l]));
					if(q2.size())
                    {
                        q1.insert(*(q2.begin()));
                        q2.erase(q2.begin());
                    }
				}
				else q2.erase(q2.find(a[l]));
				l++;	
			}	
		}
	}
	// vector<int>c;
	// for(int i=1;i<=n;i++)
	// {
	// 	for(int j=i;j<=n;j++)
	// 	{
	// 		vector<int>p;
	// 		for(int x=i;x<=j;x++)
	// 		{
	// 			for(int y=x;y<=j;y++)
	// 			{
	// 				p.push_back(b[x][y]);
	// 			}
	// 		}
	// 		sort(all(p));
	// 		c.push_back(p[(((j-i+1)*(j-i+1)-(j-i+1))/2+j-i+2)/2-1]);
	// 	}
	// }
	// sort(all(c));
	// if(c[(int)c.size()/2-1]!=c[(int)c.size()/2])cout<<"!!!!!!"<<endl;
	// else cout<<"NNNN"<<endl;
	// for(auto i:c)cout<<i<<' ';
	// cout<<endl;
    auto check=[&](int x)
    {
        int num=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(b[i][j]>=x)s[i][j]=1;
                else s[i][j]=0;
                s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=i;j<=n;j++)
            {
                int res=((j-i+1)*(j-i+1)-(j-i+1))/2+j-i+1;
                if(s[j][j]-s[i-1][j]-s[j][i-1]+s[i-1][i-1]>=res/2+1)num++;
            }
        }
        return num>=(((1+n)*n)/2+1)/2;
    };
    int l=0,r=1e9+1;
    while(l+1<r)
    {
        int mid=l+r>>1;
        if(check(mid))l=mid;
        else r=mid;
    }
    cout<<l<<endl;
}
signed main()
{
	bool multiset=0;
	//cout<<setiosflags(ios::fixed),cout.precision(2);
	ios::sync_with_stdio(0),cin.tie(0);
	int _t=1;
	if(multiset)cin>>_t;
	for(int i=1;i<=_t;i++)
	{
		solve(i);
	}
	return 0;
}