// Original C++ solution (slower):
#include <bits/stdc++.h>

#define mem(x,v) memset(x,v,sizeof(x)) 

#define go(i,a,b)  for (int i = a; i <= b; i++)

#define og(i,a,b)  for (int i = a; i >= b; i--)

#define MID(a,b) (a + b) >> 1

#define lson now << 1

#define rson now << 1 | 1

#define low(x) (x & (-x))

using namespace std;

typedef long long LL;

const double EPS = 1e-10;

const int INF = 1e9+100;

const int N = 1e6+10;

int a[N],b[N],c[N];

LL f[N];

int n,tt;

void Add(int x){

	while(x <= 3*n){

		f[x] += 1;

		x += low(x);

	}

}

int Query(int x){

	int ans = 0;

	while(x > 0) ans += f[x], x -= low(x);

	return ans; 

}

bool find(int k){

	mem(f,0);

	LL Ans = 0;	b[0] = 0;

	go(i,1,n) if (a[i] >= c[k]) b[i] = b[i-1] + 1; else b[i] = b[i-1];

	go(i,0,n) {

		b[i] = 2*b[i] - i + n + 1;

		Ans += Query(b[i]);

		Add(b[i]);

	}

	LL t = (1LL * n * (n + 1)) / 2;

	if (Ans >= (t+1)/2) return 1; 

	return 0;

}



int main(){

	scanf("%d",&n);

	int l = 1, r = n;

	go(i,1,n){

		scanf("%d",&a[i]);

		c[i] = a[i];

	}

	sort(c+1,c+n+1);

	int ans = 0;

	while(l <= r){

		int mid = MID(l,r);

		if (find(mid)) l = mid+1,ans = c[mid]; else r = mid - 1;

	}

	printf("%d\n",ans);

	return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <iostream>

#include <iomanip>

#include <string>

#include <vector>

#include <queue>

#include <map>

#include <set>



#define ll long long

#define ull unsigned long long

#define BUG printf("************\n")

using namespace std;



const ull mod = 1e8 + 7;

const int maxn = 4e5 + 10;

const int maxm = 1e6 + 10;

const double eps = 1e-8;



ll n, m;

ll a[maxn], b[maxn], s[maxn], f[maxn] ,c[maxn], r[maxn];



inline int lb(int x) {

    return x & -x;

}



void add(ll num, int x) {

    for (int i = x; i <= n; i+=lb(i))

        c[i] += num;

}



ll read(int x) {

    ll tot = 0;

    for (int i = x; i; i -= lb(i))tot += c[i];

    return tot;

}



const int cmp(const int i, const int j) {

    return f[j] == f[i] ? i < j : f[i] < f[j];

}



ll inversed_pair() {

    memset(c, 0, sizeof(c));

    for (int i = 1; i <= n; ++i)r[i] = i;

    sort(r + 1, r + 1 + n, cmp);

    ll tot = 0;

    for (int i = 1; i <= n; ++i) {

        tot += read(r[i]);

        add(1, r[i]);

    }

    return tot;

}



bool check(int x) {

    for (int i = 1; i <= n; ++i) {

        if (a[i] >= x)b[i] = 1;

        else b[i] = 0;

    }

    for (int i = 1; i <= n; ++i) {

        s[i] = s[i - 1] + b[i];

    }

    int t = 0;

    for (int i = 1; i <= n; ++i) {

        f[i] = 2 * s[i] - i;

        if (f[i] >= f[0])++t;

    }

    return (2 * (inversed_pair() + t) >= m);

}



int main() {

    ios::sync_with_stdio(0);

    cin.tie(0);

    cout.tie(0);

    cin >> n;

    for (int i = 1; i <= n; ++i) {

        cin >> a[i];

    }

    if (n == 1) {

        cout << a[1] << endl;

        return 0;

    }

    int l = 1, r = 1e9+10;

    m = (n + 1) * n / 2;

    while (l < r) {

        int mid = (l + r + 1) / 2;

        if (!check(mid))r = mid - 1;

        else l = mid;

    }

    cout << l << endl;

    return 0;

}

/*

9

7 12 4 18 3 16 18 5 9

*//*

10

16 18 12 17 15 8 10 9 16 4

 */

// Fastest known solution for this problem:
#define _USE_MATH_DEFINES



#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <cmath>

#include <algorithm>

#include <vector>

#include <queue>

#include <map>

#include <list>

#include <stack>



using namespace std;



typedef pair<long long int, long long int> P;



long long int INF = 1e18;

long long int MOD = 1e9 + 7;



long long int N, sz = 150000;

long long int A[110000];

bool flag[110000];

long long int BIT[210000];



void add(int a, long long int w){

	

	// a番目の要素にwを足す O(log N)

	

	for(int x = a; x <= sz; x += x & -x){

		BIT[x] += w;

	}

}



long long int sum(int a){

	

	// 1からaまでの要素の合計を返す O(log N)

	

	long long int ret = 0;

	for(int x = a; x > 0; x -= x & -x){

		ret += BIT[x];

	}

	return ret;

}



void init(){

	for(int i = 0; i < sz; i++){

		BIT[i] = 0;

	}

}



bool check(long long int min_A){

	for(int i = 0; i < N; i++){

		flag[i] = (A[i] >= min_A);

	}

	vector<P> v;

	long long int cnt = 0, S = 0;

	v.push_back(make_pair(0, 1));

	for(int i = 0; i < N; i++){

		if(flag[i]){

			S += 1;

		}else{

			S -= 1;

		}

		v.push_back(make_pair(S, i + 2));

	}

	sort(v.begin(), v.end());

	init();

	for(int i = 0; i < v.size(); i++){

		cnt += sum(v[i].second);

		add(v[i].second, 1);

	}

	//cout << min_A << " " << cnt << endl;

	return cnt >= (N * (N + 1) / 2 + 1) / 2;

}



long long int bin_search(long long int lef, long long int rig){

	long long int middle = (lef + rig) / 2;

	//cout << middle << " ";

	if(rig - lef <= 1){

		if(check(rig)){

			return rig;

		}else{

			return lef;

		}

	}

	if(check(middle)){

		lef = middle;

	}else{

		rig = middle;

	}

	return bin_search(lef, rig);

}



int main(){

	

	cin >> N;

	

	for(int i = 0; i < N; i++){

		cin >> A[i];

	}

	

	cout << bin_search(0, 1e10) << endl;

	

	return 0;

}