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

using namespace std;



const int maxn = 1e5+10;

int a[maxn];

int b[maxn];

int n;



int c[maxn],tmp[maxn];

long long ans;



void Merge(int l,int m,int r)

{

    int i = l;

    int j = m + 1;

    int k = l;

    while(i <= m && j <= r)

    {

        if(c[i] > c[j])

        {

            tmp[k++] = c[j++];

            ans += m - i + 1;

        }

        else

        {

            tmp[k++] = c[i++];

        }

    }

       while(i <= m) tmp[k++] = c[i++];

    while(j <= r) tmp[k++] = c[j++];

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

        c[i] = tmp[i];

}

 

void Merge_sort(int l,int r)

{

    if(l < r)

    {

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

        Merge_sort(l,m);

        Merge_sort(m+1,r);

        Merge(l,m,r);

    }

}



int lowbit(int x){

    return x&(-x);

}



void add(int x,int d){

    while(x<=n){

        b[x]+=d;

        x+=lowbit(x);

    }

}





int sum(int x){

    int res = 0;

    while(x){

        res+=b[x];

        x-=lowbit(x);

    }

    return res;

}



bool cc(int d){

    memset(b,0,sizeof(b));

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

    if(a[i]>=d)add(i,1);

    else add(i,-1);

}

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

        ans = 0;

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

            if(c[i]<0)ans++;//单个前缀和小于0

        }

        Merge_sort(1,n);//统计逆序数

        long long num = 1LL*n*(n+1)/2 - ans;

        return num>=ans;

}



int main(){

    scanf("%d",&n);

    for(int i=1;i<=n;i++)scanf("%d",&a[i]);

    int ub = 1e9;

    int lb = 0;

        while(ub-lb>1){

            int mid = lb+(ub-lb)/2;

            if(cc(mid))lb = mid;

            else ub = mid;

        }

        if(cc(lb+1))lb++;

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

    return 0;

}

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

#include<algorithm>

using namespace std;

const int MAXN = 100000;

const int INF = int(1E9);

int arr[MAXN + 5], sum[MAXN + 5], temp[MAXN + 5];

long long tot1 = 0, tot2 = 0;

int N;

void MergeSort(int le, int ri) {

    if( le == ri ) return ;

    int mid = (le + ri) >> 1;

    MergeSort(le, mid);

    MergeSort(mid+1, ri);

    int p = le, q = mid+1, r = le;

    while( p <= mid && q <= ri ) {

        if( sum[p] < sum[q] ) {

            temp[r++] = sum[p++];

        }

        else {

            tot1 += (p-le);

            temp[r++] = sum[q++];

        }

    }

    while( p <= mid ) {

        temp[r++] = sum[p++];

    }

    while( q <= ri ) {

        tot1 += (p-le);

        temp[r++] = sum[q++];

    }

    for(int i=le;i<=ri;i++)

        sum[i] = temp[i];

}

bool Check(int x) {

    tot1 = 0;

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

        sum[i] = (arr[i] <= x ? 1 : -1);

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

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

    MergeSort(0, N);

    return tot1 >= (tot2/2 + 1);

}

int main() {

    int le = INF, ri = -INF;

    scanf("%d", &N);

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

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

        le = min(le, arr[i]);

        ri = max(ri, arr[i]);

        tot2 += i;

    }

    while( le < ri ) {

        int mid = (le + ri) >> 1;

        if( Check(mid) ) ri = mid;

        else le = mid + 1;

    }

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

}