// Problem: A. 中位数
// Contest: undefined - NOIP2024训练赛 05
// URL: http://noi.ac/contest/1157/problem/2380
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Challenger: Erica N
// ----
// 
#include<bits/stdc++.h>

using namespace std;
#define rd read()
#define ull unsigned long long
#define int long long 
#define pb push_back
#define itn int
#define ps second 
#define pf first


#define rd read()
int read(){
  int xx = 0, ff = 1;char ch = getchar();
  while (ch < '0' || ch > '9'){
    if (ch == '-')ff = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')xx = xx * 10 + (ch - '0'), ch = getchar();
  return xx * ff;
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() {cerr << endl;}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) {
	for (auto v: a) cerr << v << ' ';err(x...);
}
template<typename T, typename... A>
void err(T a, A... x) {
	cerr << a << ' ';err(x...);
}
#else
#define dbg(...)
#endif
const int N=6e5+5;
const int M=3e5;
const ull P=137;
const int INF=1e18+7;
/*

策略


*/	



namespace BIT{
	int c[N];
	void change(int x,int v){
		x+=M;
		while(x<N){
			c[x]+=v;
			x+=x&-x;
		}
	}
	int query(int x){
		x+=M;
		int res=0;
		while(x){
			res+=c[x];
			x-=x&-x;
		}
		return res;
	}

}using namespace BIT;

int pre[N];
int a[N],b[N];
int n;

int check(int x){
	for(int i=1;i<=n;i++){
		pre[i]=pre[i-1]+(a[i]>=x);
	}
	
	memset(c,0,sizeof c);
	int res=0;
	change(0,1);
	for(int i=1;i<=n;i++){
		res+=query(i/2-pre[i]);
	// cdbg("UJD",i);
		change(i/2-pre[i],1);
	}
	
	// cdbg(x,res);
	return res;
}

signed main(){
	 n=rd;
	for(int i=1;i<=n;i++){
		b[i]=a[i]=rd;
	}
	
	int tot=(1+n)*n/2;
	sort(b+1,b+n+1);
	int len=unique(b+1,b+n+1)-b-1;
	int l=1,r=len;
	int res=0;
	
	// cdbg(tot);
	
	
	// cdbg("OK");
	while(l<=r){
		int mid=l+r>>1;
		// cdbg(l,r);
		if(check(b[mid])>=tot/2)res=mid,r=mid-1;
		else l=mid+1;
	}
	
	cout<<b[res]<<endl;
	
	
}