// Slower C++ solution:
#include<bits/stdc++.h>



#define LL long long

#define int long long

#define RG register



using namespace std;

template<class T> inline void read(T &x) {

	x = 0; RG char c = getchar(); bool f = 0;

	while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c == '-') c = getchar(), f = 1;

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

	x = f ? -x : x;

	return ;

}

template<class T> inline void write(T x) {

	if (!x) {putchar(48);return ;}

	if (x < 0) x = -x, putchar('-');

	int len = -1, z[20]; while (x > 0) z[++len] = x%10, x /= 10;

	for (RG int i = len; i >= 0; i--) putchar(z[i]+48);return ;

}

const int N = 1e5 + 10;

int a[N], b[N], n, m, c[N], cnt[N], t[N * 2];

int lowbit(int x) {

	return x & (-x);

}

void add(int x) {

//	printf("add %d\n", x- N);

	for (; x <= n + N; x += lowbit(x)) t[x]++;

}

int sum(int x) {

//	printf("sum %d\n", x - N);

	int res = 0;

	for (; x; x -= lowbit(x)) res += t[x];

	return res;

}

int check(int x) {

	memset(t, 0, sizeof(t));

	for (int i = 1; i <= n; i++) if (b[x] < a[i]) c[i] = 1; else c[i] = 0;

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

		cnt[i] = cnt[i - 1] + (c[i] == 1 ? 1 : -1);

	int ans = 0;

	add(N);

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

		ans += sum(cnt[i] + N);

		add(N + cnt[i]);

	}

	return ans;	

}

 main() {

	//freopen(".in", "r", stdin);

	//freopen(".out", "w", stdout);

	read(n);

	for (int i = 1; i <= n; i++) read(a[i]), b[i] = a[i];

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

	m = unique(b + 1, b + 1 + n) - b - 1;

	int l = 1, r = m, ans = 0, cnt = n * (n - 1) / 2 + n;

	while (l <= r) {

		int mid = (l + r) >> 1;

		if (cnt - check(mid) >= (cnt / 2 + 1)) ans = mid, r = mid - 1;

		else l = mid + 1;

	}

	printf("%lld\n", b[ans]);

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 2.5336527672554814x):
#include <cstdio>

#include <cstring>

#include <algorithm>

#define ll long long

#define inf 1<<30

#define il inline 

#define in1(a) read(a)

#define in2(a,b) in1(a),in1(b)

#define in3(a,b,c) in2(a,b),in1(c)

#define in4(a,b,c,d) in2(a,b),in2(c,d)

il void readl(ll &x){

    x=0;ll f=1;char c=getchar();

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

    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}

    x*=f;

}

il void read(int &x){

    x=0;int f=1;char c=getchar();

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

    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}

    x*=f;

}

using namespace std;



#define N 100010

#define lowbit(x) x&-x

int c[N*10];

int n,a[N],s[N*10];

void add(int x){

    for(int i=x;i<=2*N;i+=lowbit(i))c[i]++;

}

ll query(int x){

    ll sum=0;

    for(int i=x;i>0;i-=lowbit(i))sum+=c[i];

    return sum;

}

bool check(int x){

    for(int i=1;i<=2*N;i++)c[i]=0;

    s[0]=0;

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

        s[i]=s[i-1]+(a[i]>=x?1:-1);

    ll sum=0;

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

        sum+=query(s[i]+N);

        add(s[i]+N);

    }

    return sum>=1ll*n*(n+1)/4;

}

int main(){

    in1(n);

    int l=0,r=0;

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

        in1(a[i]);

        r=max(r,a[i]);

    }

    int ans=0;

    while(l<=r){

        int mid=(l+r)>>1;

        if(check(mid))l=mid+1;

        else r=mid-1;

    }

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

}