#include<bits/stdc++.h>
using namespace std;
int a[2010],b[2010][2010],tmp[2010][2010];
int n;
int check(int mid)//mid大于等于中位数的时候返回真
{
	memset(tmp,0,sizeof tmp);
	for(int i=1;i<=n;i++)
	{
		for(int j=i;j<=n;j++)
		{
			if(b[i][j]>mid) tmp[i][j]=1;
			else tmp[i][j]=0; 
		}
	}

	for(int i=1;i<=n;i++)
		for(int j=i;j<=n;j++)
			tmp[i][j] += tmp[i][j-1];
	
	for(int i=n-1;i>=1;i--)
		for(int j=i;j<=n;j++)
			tmp[i][j] += tmp[i+1][j];
	
//	for(int i=1;i<=n;i++) 
//	{
//		for(int j=i;j<=n;j++) printf("%d ",tmp[i][j]);
//		printf("\n");
//	}
	int ans=0,t=0; 
	for(int i=1;i<=n;i++)
	{
		for(int j=i;j<=n;j++)
		{
			if(tmp[i][j]*2 <= (1+j-i+1)*(j-i+1)/2) ans++;
			else t++;
		}
	}
	if(ans >=  t) return 1;
	else return 0;
}
int main()
{
	scanf("%d",&n);
	int l=0x3f3f3f3f,r=-0x3f3f3f3f;
	for(int i=1;i<=n;i++) 
	{
		scanf("%d",&a[i]);
		l=min(a[i],l);
		r=max(a[i],r);
	}
	for(int i=1;i<=n;i++)
	{
		priority_queue<int>big;
		priority_queue<int,vector<int>,greater<int>>small;
		int c=0;
		for(int j=i;j<=n;j++)
		{
			if(!big.size()||big.top()>=a[j])  big.push(a[j]);
			else small.push(a[j]);
			c++;
			int mid=ceil(c*1.0/2);
			while((int)big.size() > mid) 
			{
				small.push(big.top());
				big.pop();
			}
			while((int)big.size() < mid)
			{
				big.push(small.top());
				small.pop();
			}
			b[i][j]=big.top();
		}
	}
//	for(int i=1;i<=n;i++) 
//	{
//		for(int j=i;j<=n;j++) printf("%d ",b[i][j]);
//		printf("\n");
//	}
	while(l<r)
	{
		int mid=(l+r)/2;  
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	printf("%d",l);
}