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

using namespace std;

typedef long long LL;

const int N = 1e5;

int a[N+5];

struct ft{

	int ft[2*N+10];

	void init(){

		memset(ft, 0, sizeof(ft));

	}

	void update(int i, int v){

		for(;i<=2*N+5;i+=(i&-i)){

			ft[i] += v;

		}

	}

	int query(int i){

		int res = 0;

		for(;i>0;i-=(i&-i)) res+=ft[i];

		return res;

	}

}ft;

int main(){

	int n;

	scanf("%d", &n);

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

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

	}

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

	LL m = tot/2+1;



	int lo = 1, hi = 1e9, ans = 0;

	while(lo <= hi){

		int mid = (lo+hi)/2;



		int cnt = 100001;

		LL res = 0;

		ft.init();

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

			ft.update(cnt, 1);

			if(a[i] <= mid) cnt++;

			else cnt--;

			res += ft.query(cnt-1);

		}



		if(res >= m) ans = mid, hi = mid-1;

		else lo = mid+1;

	}

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

}

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

#include <cstring>

#include <algorithm>

#include <cassert>

const int MAXN = 1e5 + 10;

typedef int IntAr[MAXN];

typedef long long LL;



int N;

IntAr A, B, C, D;

LL tot;



namespace FastIO {

	template <typename T>

	void read(T & x) {

		x = 0; register char ch = getchar();

		for (; ch < '0' || ch > '9'; ch = getchar());

		for (; ch >= '0' && ch <= '9'; x = (x << 3) + (x << 1) + (ch ^ '0'), ch = getchar());

	}

}

LL count(int);

void merge(int l, int r);



// #define DEBUG_MD_



int main() {

	using FastIO::read;

	read(N);

	for (int i = 0; i < N; i++) scanf("%d", &A[i]);

	memcpy(B, A, sizeof(int) * N);

	std::sort(B, B + N);

	int lb = -1, mid, ub = std::unique(B, B + N) - B - 1;

	LL pos = (LL(N) * (N + 1) >> 2) + 1;

#ifdef DEBUG_MD_

	printf("pos=%lld\n", pos);

#endif 

	for (; ub - lb > 1; ) { // (lb, ub]

		mid = lb + ub >> 1;

		assert(mid >= 0);

		if (count(B[mid]) >= pos) ub = mid;

		else lb = mid;

	}

	// return 0;

	printf("%d\n", B[ub]);

	return 0;

}



LL count(int key) {

	C[0] = 0;

	for (int i = 1; i <= N; i++) C[i] = C[i - 1] + (A[i - 1] > key ? -1 : 1);

	tot = 0;

	merge(0, N + 1);

#ifdef DEBUG_MD_

	printf("key=%d, tot=%lld\n", key, tot);

#endif 

	return tot;

}



void merge(int l, int r) {

	// merge sort interval [l, r)

	if (r - l <= 1) return;

	int mid = l + r >> 1;

	merge(l, mid);

	merge(mid, r);

#ifdef DEBUG_MD_

	printf("[%d, %d)\n", l, r);

#endif

	int i, j, k;

	for (i = l, j = mid, k = l; i < mid && j < r; )

		if (C[i] < C[j]) {

			D[k++] = C[i++];

			tot += r - j;

		}

		else D[k++] = C[j++];

	for (; i < mid; ) D[k++] = C[i++];

	for (; j < r; ) D[k++] = C[j++];

	memcpy(C + l, D + l, sizeof(int) * (r - l));

}

// 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;

}