// Original C++ solution (slower):
#include <cstdio>

#include <cstring>

#include <algorithm>

#define ll long long

#define inf 1<<30

#define il inline 

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(){

    read(n);

    int l=0,r=0;

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

        read(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);

}


// Optimized solution to the same problem (faster):
//

// Copyright 2020 TuringEdu. All Rights Reserved.

//

// FileName: C.cc

// Author: Beiyu Li <sysulby@gmail.com>

// Date: 2020-06-16

//

#include <bits/stdc++.h>

#include <bits/extc++.h>



using namespace std;



#define rep(i, n) for (int i = 0; i < (n); ++i)

#define For(i, s, t) for (int i = (s); i <= (t); ++i)



using LL = long long;

using Pii = pair<int, int>;

template <typename T>

using Heap = __gnu_pbds::priority_queue<T, greater<T>,

      __gnu_pbds::pairing_heap_tag>;

template <typename T>

using BST = __gnu_pbds::tree<T, __gnu_pbds::null_type, less<T>,

      __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;



const int inf = 0x3f3f3f3f;

const LL infLL = 0x3f3f3f3f3f3f3f3fLL;



const int maxn = 100000 + 5;



int n;

int a[maxn];

int vec[maxn], sz;

int s[maxn], t[maxn];



LL merge_sort(int l, int r) {

  if (l == r) return 0;

  int mid = (l + r) / 2;

  LL ret = merge_sort(l, mid) + merge_sort(mid + 1, r);

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

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

    if (j > r || (i <= mid && s[i] <= s[j])) t[p++] = s[i++];

    else t[p++] = s[j++], ret += mid - i + 1;

  }

  For(i,l,r) s[i] = t[i];

  return ret;

}



bool check(int x) {

  s[0] = 0;

  For(i,1,n) s[i] = s[i-1] + (a[i] < x? -1: 1);

  return merge_sort(0, n) * 2 <= (LL)n * (n + 1) / 2;

}



int main() {

  scanf("%d", &n);

  For(i,1,n) {

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

    vec[sz++] = a[i];

  }

  sort(vec, vec + sz);

  sz = unique(vec, vec + sz) - vec;

  int l = 0, r = sz - 1;

  while (l < r) {

    int mid = (l + r + 1) / 2;

    if (check(vec[mid])) l = mid;

    else r = mid - 1;

  }

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



  return 0;

}

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

}