#include<bits/stdc++.h>

using namespace std;

const int N = 3e5+5;

int n;
int a[N];
vector<int> all;
//multiset<int> st;
mt19937 rnd(210828);
struct Fhq_Treap{
	int v[N],_;
	int siz[N],key[N],rt;
	int ch[N][2];
	void clear(){
		rt=0,_=0;
	}
	int newnode(int x){
		v[++_]=x,key[_]=rnd(),siz[_]=1,ch[_][0]=ch[_][1]=0;return _;
	}
	void pushup(int x){siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;}
	void split_v(int now,int val,int &x,int &y){
		if(!now) x=y=0;
		else{
			if(v[now]<=val){
				x=now;
				split_v(ch[x][1],val,ch[x][1],y);
			}
			else{
				y=now;
				split_v(ch[y][0],val,x,ch[y][0]);
			}
			pushup(now);
		}
	}
	void split_s(int now,int s,int &x,int &y){
		if(!now) x=y=0;
		else{
			if(siz[ch[now][0]]+1<=s){
				x=now;
				split_s(ch[now][1],s-(siz[ch[now][0]]+1),ch[now][1],y);
			}
			else{
				y=now;
				split_s(ch[now][0],s,x,ch[now][0]);
			}
			pushup(now);
		}
	}
	int merge(int x,int y){
		if(!x||!y) return x|y;
		if(key[x]<key[y]){
			ch[x][1]=merge(ch[x][1],y);
			pushup(x);
			return x;
		}
		ch[y][0]=merge(x,ch[y][0]);
		pushup(y);
		return y;
	}
	int x,y,z;
	void insert(int val){
		split_v(rt,val,x,y);
		rt=merge(merge(x,newnode(val)),y);
	}
	int mid(){
		int sz=siz[rt];
//		cout<<sz<<':';
		int k=(sz+1)/2;
		split_s(rt,k-1,x,y);
		split_s(y,1,y,z);
//		cout<<siz[y]<<'?';
		int re=v[y];
		rt=merge(merge(x,y),z);
		return re;
	}
	void ldr(int x){
		if(ch[x][0]) ldr(ch[x][0]);
		cout<<v[x]<<' ';
		if(ch[x][1]) ldr(ch[x][1]);
	}
}st;

int main(){
//	freopen("ex_median2.in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++){
		st.clear();
		for(int j=i;j<=n;j++){
			st.insert(a[j]);
//			cout<<i<<' '<<j<<' '<<st.mid()<<' ';
//			st.ldr(st.rt);cout<<'\n';
			all.push_back(st.mid());
		}
	}
//	for(auto i:all)
//		cout<<i<<' ';
	sort(all.begin(),all.end());
	if(all.size()%2==1)
		cout<<all[all.size()/2+1];
	else
		cout<<all[(all.size()+1)/2];
	
	return 0;
}

answer.code:11:1: error: 'mt19937' does not name a type
 mt19937 rnd(210828);\x0d
 ^
answer.code: In member function 'int Fhq_Treap::newnode(int)':
answer.code:20:23: error: 'rnd' was not declared in this scope
   v[++_]=x,key[_]=rnd(),siz[_]=1,ch[_][0]=ch[_][1]=0;return _;\x0d
                       ^