// Original C++ solution (slower):
// ===================================

//   author: M_sea

//   website: http://m-sea-blog.com/

// ===================================

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <vector>

#include <cmath>

#define re register

using namespace std;

typedef long long ll;



inline int read() {

    int X=0,w=1; char c=getchar();

    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }

    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();

    return X*w;

}



const int N=100000+10;

const int LIM=100005;



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



int c[(LIM<<1)+10];

inline void add(int x,int y) { for (;x<=LIM<<1;x+=x&-x) c[x]+=y; }

inline int sum(int x) { int s=0; for (;x;x-=x&-x) s+=c[x]; return s; }



inline ll calc(int mid) {

    for (re int i=1;i<=n;++i) b[i]=a[i]<mid?-1:1;

    for (re int i=2;i<=n;++i) b[i]+=b[i-1];

    memset(c,0,sizeof(c)); add(LIM,1); ll res=0;

    for (re int i=1;i<=n;++i) res+=i-sum(b[i]+LIM),add(b[i]+LIM,1);

    return res;

}



inline int check(int mid) { return calc(S[mid])<1ll*n*(n+1)/2/2+1; }



int main() {

    n=read();

    for (re int i=1;i<=n;++i) S[i]=a[i]=read();

    sort(S+1,S+n+1); int top=unique(S+1,S+n+1)-S-1;

    int L=1,R=top;

    while (L<R) {

        int mid=(L+R+1)>>1;

        if (check(mid)) L=mid;

        else R=mid-1;

    }

    printf("%d\n",S[L]);

    return 0;

}


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

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<vector>

#include<set>

#include<map>

#include<unordered_set>

#include<unordered_map>

#include<queue>

#include<ctime>

#include<cassert>

#include<complex>

#include<string>

#include<cstring>

#include<chrono>

#include<random>

#include<bitset>

#include<iomanip>



#define fi first

#define se second

#define mp make_pair

#define eb emplace_back

#define all(v) v.begin(), v.end()

#define sz(v) (int) v.size()



using namespace std;



mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());



typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

typedef pair<int, int> pii;



const int MAX_N = 1e5 + 5;



int n, a[MAX_N];

int pref[MAX_N], fenw[MAX_N * 2];



void update(int pos, int delta) {

	for (int i = pos; i <= 2 * n; i |= (i + 1)) {

		fenw[i] += delta;

	}

}



int get(int r) {

	int res = 0;

	for (int i = r; i >= 0; i = (i & (i + 1)) - 1) {

		res += fenw[i];

	}

	return res;

}



bool check(int m) {

	fill(fenw, fenw + 2 * n + 1, 0);

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

		pref[i] = pref[i - 1] + (a[i] >= m) - (a[i] < m);

	}

	update(n, 1);

	ll cnt = 0;

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

		cnt += get(pref[i] + n);

		update(pref[i] + n, 1);

	}

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

}



signed main() {

	ios_base::sync_with_stdio(0);

	cin.tie(0);

	cin >> n;

	vector<int> diff;

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

		cin >> a[i];

		diff.eb(a[i]);

	}

	sort(all(diff));

	diff.resize(unique(all(diff)) - diff.begin());

	int lef = 0, rig = sz(diff);

	while (lef + 1 < rig) {

		int mid = (lef + rig) / 2;

		if (check(diff[mid])) {

			lef = mid;

		} else {

			rig = mid;

		}

	}

	cout << diff[lef] << "\n";

	return 0;

}

// Fastest known solution for this problem: