// Slower C++ solution:
#include <iostream>

#include <queue>

#include <vector>

#include <map>

#include <set>

#include <cstring>

using namespace std;

typedef long long ll;

ll ans;

int n,val[100005],c[100005],pre[100005];

void merge(int a[],int l,int r){

    if(l==r)

        return;

    int mid = (l+r)/2;

    merge(a,l,mid);

    merge(a,mid+1,r);

    int i=l,j=mid+1,index=l;

    while (i<=mid&&j<=r){

        if(a[i]>a[j]){

            c[index++]=a[j];

            ans+=mid-i+1;

            j++;

        } else{

            c[index++]=a[i];

            i++;

        }

    }

    while (i<=mid)

        c[index++]=a[i++];

    while (j<=r)

        c[index++]=a[j++];

    for(int i=l;i<=r;i++)

        a[i]=c[i];

}

bool check(int mid){

    //memset(pre,0, sizeof(pre));

    ans = 0;//逆序对的数量

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

        if(val[i]<mid)

            pre[i]=pre[i-1]-1;

        else

            pre[i]=pre[i-1]+1;

        if(pre[i]<0)

            ans++;

    }

    merge(pre,1,n);

    ll all = 1ll*n*(n+1)/2;

    return all>=2*ans;

}

int main(){

    ios::sync_with_stdio(false);

    cin>>n;

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

        cin>>val[i];

    }

    int l = 1,r = 1e9;

    while (l+1<r){

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

        if(check(mid)){//增加的区间大于等于一半了(数偏小

            l=mid;

        } else

            r=mid;

    }

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

    cout<<l<<endl;

}




// Faster C++ solution for the same problem (measured speedup: 5.236825118912459x):
#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));

}