#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;

inline int read(){
	int sum=0,f=1;char ch=getchar();
	while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
	return f*sum;
}

const int N=100001;
struct tree{int l,r,cnt;}t[N<<2];
int n,a[N],ans,ok,rt[N];
int c[N],tot;

inline int build(int l,int r){
	int p=++tot;
	if(l==r) return p;
	int mid=(l+r)>>1;
	t[p].l=build(l,mid);t[p].r=build(mid+1,r);
	return p;
}

inline int update(int p,int l,int r,int k){
	int x=++tot;t[x]=t[p];t[x].cnt++;
	if(l==r) return x;
	int mid=(l+r)>>1;
	if(k<=mid) t[x].l=update(t[p].l,l,mid,k);
	else t[x].r=update(t[p].r,mid+1,r,k);
	return x;
}

inline int query(int pl,int pr,int l,int r,int k){
	if(l==r) return l;
	int sum=t[t[pr].l].cnt-t[t[pl].l].cnt,mid=(l+r)>>1;
	if(sum>=k) return query(t[pl].l,t[pr].l,l,mid,k);
	else return query(t[pl].r,t[pr].r,mid+1,r,k-sum);
}

inline void add(int p,int l,int r,int k){
	t[p].cnt++;
	if(l==r) return ;
	int mid=(l+r)>>1;
	if(k<=mid) add(t[p].l,l,mid,k);
	else add(t[p].r,mid+1,r,k);
}

int main(){
	n=read();
	for(int i=1;i<=n;i++) a[i]=read(),c[i]=a[i];
	sort(c+1,c+n+1);int m=unique(c+1,c+n+1)-c-1;
	for(int i=1;i<=n;i++) a[i]=lower_bound(c+1,c+m+1,a[i])-c;
	rt[0]=build(1,n);rt[n+1]=build(1,n);
	for(int i=1;i<=n;i++) rt[i]=update(rt[i-1],1,n,a[i]);   
	for(int l=1;l<=n;l++){
		for(int r=l;r<=n;r++){
			int len=(r-l+1);int k=(len>>1)+1;
			int mid=query(rt[l-1],rt[r],1,n,k);
//			printf("l=%d r=%d k=%d mid=%d\n",l,r,k,mid);
			add(rt[n+1],1,n,mid);
		}
	}
	printf("%d\n",c[query(rt[0],rt[n+1],1,n,((n*(n+1))>>2)+1)]);
	return 0;
}
