stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <iostream>

#include <stdio.h>

#include <cstring>

#include <algorithm>

#define ll long long

#define rep(i, a, b) for(int i = (a); i <= (b); i++)

using namespace std;

const int N = 1e5 + 9, M = 2e5 + 9;

const int inf = 0x3f3f3f3f;

int a[N], s[N], tr[M], n;

int lowbit(int x) { return x & (-x); }

void add(int x){ while(x < M) tr[x]++, x += lowbit(x); }

ll query(int x){

    ll res = 0;

    while(x > 0) res += tr[x], x -= lowbit(x);

    return res;

}

bool check(int x){

    ll res = 0;

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

    memset(tr, 0, sizeof tr);

    rep(i, 0, n) res += query(s[i] + N), add(s[i] + N);

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

}

int erfen(int l, int r){

    int res = 0;

    while(l <= r){

        int mid = (l + r) / 2;

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

        else r = mid-1;

    }

    return res;

}

int main(){

    int minn = inf, maxx = 0;

    scanf("%d", &n);

    rep(i, 1, n) {

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

        maxx = max(maxx, a[i]), minn = min(minn, a[i]);

    }

    printf("%d", erfen(minn, maxx));

    return 0;

}

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

#include <sstream>

#include <algorithm>

#include <cstdio>

#include <cmath>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <cstring>

#include <bitset>

#include <functional>

#include <random>

#define REP(i,a,n) for(int i=a;i<=n;++i)

#define PER(i,a,n) for(int i=n;i>=a;--i)

#define hr putchar(10)

#define pb push_back

#define lc (o<<1)

#define rc (lc|1)

#define mid ((l+r)>>1)

#define ls lc,l,mid

#define rs rc,mid+1,r

#define x first

#define y second

#define io std::ios::sync_with_stdio(false)

#define endl '\n'

#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<',';hr;})

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

const int P = 1e9+7, INF = 0x3f3f3f3f;

ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}

ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}

ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}

inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}

//head







const int N = 1e6+50;

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

int f[2*N], *cnt = f+N;



//求出中位数>=x的子区间个数

ll calc(int x) {

	REP(i,-n,n) cnt[i] = 0;

	ll ans = 0;

	int ret = 0, sum = 0, pos = 0;

	//ret维护0<=j<=i-1, s[j]<=s[i]的j的个数

	REP(i,1,n) {

		++cnt[sum], ++ret;

		if (a[i]>=x) ret += cnt[++sum];

		else ret -= cnt[sum--];

		ans += ret;

	}

	return ans;

}



int main() {

	scanf("%d", &n);

	REP(i,1,n) scanf("%d",a+i),b[i]=a[i];

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

	int l=1,r=n,ans;

	ll m = (n+1ll)*n/2, pos = (m+1)/2;

	while (l<=r) {

		if (calc(b[mid])>=pos) ans=mid,l=mid+1;

		else r=mid-1;

	}

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

}
// Slower C++ solution:
//hahaha

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define int long long

#define N 100002

using namespace std;

int n,i,a[N],b[N],c[N*2],sum[N],l=0,r,mid,ans;

int read()

{

	char c=getchar();

	int w=0;

	while(c<'0'||c>'9') c=getchar();

	while(c<='9'&&c>='0'){

		w=w*10+c-'0';

		c=getchar();

	}

	return w;

}

int lowbit(int x)

{

	return x&(-x);

}

void add(int x,int y)

{

	for(int i=x;i<=200000;i+=lowbit(i)) c[i]+=y;

}

long long ask(int x)

{

	long long ans=0;

	for(int i=x;i>=1;i-=lowbit(i)) ans+=c[i];

	return ans;

}

bool check(int x)

{

	sum[0]=100000;

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

		if(a[i]>=x) sum[i]=sum[i-1]+1;

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

	}

	memset(c,0,sizeof(c));

	long long ans=0;

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

		ans+=ask(sum[i]);

		add(sum[i],1);

	}

	return (ans>=1LL*n*(n+1)/4);

}

signed main()

{

	n=read();

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

		a[i]=read();

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

	}

	while(l<=r){

		mid=(l+r)/2;

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

		else r=mid-1;

	}

	cout<<ans<<endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.120054961807859x):
#include<bits/stdc++.h>

using namespace std;

//#include<ext/rope>

//using namespace __gnu_cxx

//#include<ext/pb_ds/priority_queue.hpp>

//using namespace __gnu_pbds;

#define lowbit(x) (x&-x)

#define pb push_back

#define empb emplace_back

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

#define clr(a,b) memset(a,b,sizeof(a))

#define caze(T) for(cin>>T;T;T--)

#define inf (1<<29)

#define Endl ('\n')

#define fi first

#define se second

#define db double

#define ldb long double

#define ll long long

#define pii pair<int,int>

#define pil pair<int,ll>

#define pli pair<ll,int>

#define pll pair<ll,ll>

#define ull unsigned long long

#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)

inline char nc() {

	#define SZ 1000000

	static char buf[SZ], *p1, *p2;

	return p1==p2&&(p2=(p1=buf)+fread(buf,1,SZ,stdin),p1==p2)?EOF:*p1++;

}

template<typename T>

inline int scan(T &x) {

	char c, sign=1; 

	while(!isdigit(c=nc())&&c!=EOF)if(c=='-')sign*=-1;

	if(c==EOF) return EOF;

	for(x = 0; isdigit(c); c = nc())

		x = (x<<1) + (x<<3) + (c&15);

	return x *= sign, 1;

}

template<typename T, typename...Args>

inline int scan(T &x, Args&...args) {

	return scan(x), scan(args...);

}

const int N=1<<18;

const int zero=1<<17;

int t[N],a[N],n;

int b[N],cc;

void add(int x,int v){for(;x<N;t[x]+=v,x+=lowbit(x));}

int sum(int x){int ret=0;while(x)ret+=t[x],x-=lowbit(x);return ret;}

int sum(int l,int r){return sum(r)-sum(l-1);}

ll calc(int x)

{

	int y=zero;

	ll ret=0;

	clr(t,0);

	add(zero,1);

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

	{

		y+=(a[i]<=x?1:-1);

		ret+=sum(y-1);

		add(y,1);

	}

	return ret;

} 

int main()

{IOS;

	cin>>n;cc=0;

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

		cin>>a[i],b[++cc]=a[i];

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

	cc=unique(b+1,b+1+cc)-b-1;

	int L=1,R=cc,mid;

	ll ans,tp;

	ll ok=1LL*(n+1)*n/4+1;

	while(R>=L)

	{

		mid=(L+R)>>1;

		if((tp=calc(b[mid]))>=ok)

			ans=b[mid],R=mid-1;

		else L=mid+1;

	}

	cout<<ans<<Endl;

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

#define FOR(i,k,n)  for(int i = (k);i < (n);++i)

#define REP(i,n)    FOR(i,0,n)

#define ALL(x)      begin(x),end(x)



using namespace std;

using vecint = vector<int>;

using ll = int64_t;



using Data = int;

const int len = 1 << 18;



struct BIT {

  vector<Data> data;

  BIT() : data(len, 0) {}

  void update(int i, Data value) {

    for (; i < len; i |= i+1) data[i] += value;

  }

  Data query(int i) {

    Data s = 0;

    for (; i >= 0; i = (i&i+1)-1) s += data[i];

    return s;

  }

};



bool ok(const vecint& a, const int th) {

  ll n = a.size();

  BIT bit;

  int offset = n;

  ll cnt = 0;

  REP(i,n) {

    bit.update(offset, 1);

    if (a[i] >= th) {

      offset -= 1;

    } else {

      offset += 1;

    }

    cnt += bit.query(offset-1);

  }

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

  ll mid = m/2 + 1;

  return cnt >= mid;

}



int main()

{

  int n;

  cin>>n;

  vecint a(n);

  REP(i,n) cin>>a[i];

  vecint b = a;

  b.push_back(0);

  b.push_back(1000000007);

  sort(ALL(b));

  b.erase(unique(ALL(b)), end(b));

  int hi = b.size()-1;

  int lo = 0;

  while ((hi - lo) > 1) {

    int mid = (hi + lo) / 2;

    if (ok(a, b[mid])) {

      hi = mid;

    } else {

      lo = mid;

    }

  }

  cout << b[lo] << endl;

  return 0;

}


// Faster C++ solution for the same problem (measured speedup: 3.0994109739042117x):
#include <bits/stdc++.h>

#define FOR(i,k,n)  for(int i = (k);i < (n);++i)

#define REP(i,n)    FOR(i,0,n)

#define ALL(x)      begin(x),end(x)



using namespace std;

using vecint = vector<int>;

using ll = int64_t;



using Data = int;

const int len = 1 << 18;



struct BIT {

  vector<Data> data;

  BIT() : data(len, 0) {}

  void update(int i, Data value) {

    for (; i < len; i |= i+1) data[i] += value;

  }

  Data query(int i) {

    Data s = 0;

    for (; i >= 0; i = (i&i+1)-1) s += data[i];

    return s;

  }

};



bool ok(const vecint& a, const int th) {

  ll n = a.size();

  vecint v(n*4);

  int offset = n*2;

  ll cnt = 0;

  ll sum = 0;

  REP(i,n) {

    v[offset] += 1;

    if (a[i] >= th) {

      offset -= 1;

      sum -= v[offset];

    } else {

      sum += v[offset];

      offset += 1;

    }

    cnt += sum;

  }

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

  ll mid = m/2 + 1;

  return cnt >= mid;

}



int main()

{

  int n;

  cin>>n;

  vecint a(n);

  REP(i,n) cin>>a[i];

  vecint b = a;

  b.push_back(0);

  b.push_back(1000000007);

  sort(ALL(b));

  b.erase(unique(ALL(b)), end(b));

  int hi = b.size()-1;

  int lo = 0;

  while ((hi - lo) > 1) {

    int mid = (hi + lo) / 2;

    if (ok(a, b[mid])) {

      hi = mid;

    } else {

      lo = mid;

    }

  }

  cout << b[lo] << endl;

  return 0;

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

#define FOR(i,k,n)  for(int i = (k);i < (n);++i)

#define REP(i,n)    FOR(i,0,n)

#define ALL(x)      begin(x),end(x)



using namespace std;

using vecint = vector<int>;

using ll = int64_t;



using Data = int;

const int len = 1 << 18;



struct BIT {

  vector<Data> data;

  BIT() : data(len, 0) {}

  void update(int i, Data value) {

    for (; i < len; i |= i+1) data[i] += value;

  }

  Data query(int i) {

    Data s = 0;

    for (; i >= 0; i = (i&i+1)-1) s += data[i];

    return s;

  }

};



bool ok(const vecint& a, const int th) {

  ll n = a.size();

  BIT bit;

  int offset = n;

  ll cnt = 0;

  REP(i,n) {

    bit.update(offset, 1);

    if (a[i] >= th) {

      offset -= 1;

    } else {

      offset += 1;

    }

    cnt += bit.query(offset-1);

  }

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

  ll mid = m/2 + 1;

  return cnt >= mid;

}



int main()

{

  int n;

  cin>>n;

  vecint a(n);

  REP(i,n) cin>>a[i];

  vecint b = a;

  b.push_back(0);

  b.push_back(1000000007);

  sort(ALL(b));

  b.erase(unique(ALL(b)), end(b));

  int hi = b.size()-1;

  int lo = 0;

  while ((hi - lo) > 1) {

    int mid = (hi + lo) / 2;

    if (ok(a, b[mid])) {

      hi = mid;

    } else {

      lo = mid;

    }

  }

  cout << b[lo] << endl;

  return 0;

}


// Faster C++ solution for the same problem (measured speedup: 3.0993775581458993x):
#include <bits/stdc++.h>

#define FOR(i,k,n)  for(int i = (k);i < (n);++i)

#define REP(i,n)    FOR(i,0,n)

#define ALL(x)      begin(x),end(x)



using namespace std;

using vecint = vector<int>;

using ll = int64_t;



bool ok(const vecint& a, const int th) {

  ll n = a.size();

  vecint v(n*4);

  int offset = n*2;

  ll cnt = 0;

  ll sum = 0;

  REP(i,n) {

    v[offset] += 1;

    if (a[i] >= th) {

      offset -= 1;

      sum -= v[offset];

    } else {

      sum += v[offset];

      offset += 1;

    }

    cnt += sum;

  }

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

  ll mid = m/2 + 1;

  return cnt >= mid;

}



int main()

{

  int n;

  cin>>n;

  vecint a(n);

  REP(i,n) cin>>a[i];

  vecint b = a;

  b.push_back(0);

  b.push_back(1000000007);

  sort(ALL(b));

  b.erase(unique(ALL(b)), end(b));

  int hi = b.size()-1;

  int lo = 0;

  while ((hi - lo) > 1) {

    int mid = (hi + lo) / 2;

    if (ok(a, b[mid])) {

      hi = mid;

    } else {

      lo = mid;

    }

  }

  cout << b[lo] << endl;

  return 0;

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

#define FOR(i,k,n)  for(int i = (k);i < (n);++i)

#define REP(i,n)    FOR(i,0,n)

#define ALL(x)      begin(x),end(x)



using namespace std;

using vecint = vector<int>;

using ll = int64_t;



using Data = int;

const int len = 1 << 18;



struct BIT {

  vector<Data> data;

  BIT() : data(len, 0) {}

  void update(int i, Data value) {

    for (; i < len; i |= i+1) data[i] += value;

  }

  Data query(int i) {

    Data s = 0;

    for (; i >= 0; i = (i&i+1)-1) s += data[i];

    return s;

  }

};



bool ok(const vecint& a, const int th) {

  ll n = a.size();

  BIT bit;

  int offset = n;

  ll cnt = 0;

  REP(i,n) {

    bit.update(offset, 1);

    if (a[i] >= th) {

      offset -= 1;

    } else {

      offset += 1;

    }

    cnt += bit.query(offset-1);

  }

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

  ll mid = m/2 + 1;

  return cnt >= mid;

}



int main()

{

  int n;

  cin>>n;

  vecint a(n);

  REP(i,n) cin>>a[i];

  vecint b = a;

  b.push_back(0);

  b.push_back(1000000007);

  sort(ALL(b));

  b.erase(unique(ALL(b)), end(b));

  int hi = b.size()-1;

  int lo = 0;

  while ((hi - lo) > 1) {

    int mid = (hi + lo) / 2;

    if (ok(a, b[mid])) {

      hi = mid;

    } else {

      lo = mid;

    }

  }

  cout << b[lo] << endl;

  return 0;

}


// Faster C++ solution for the same problem (measured speedup: 3.0604318557711023x):
#include <bits/stdc++.h>

#define FOR(i,k,n)  for(int i = (k);i < (n);++i)

#define REP(i,n)    FOR(i,0,n)

#define ALL(x)      begin(x),end(x)



using namespace std;

using vecint = vector<int>;

using ll = int64_t;



bool ok(const vecint& a, const int th) {

  ll n = a.size();

  vecint v(n*4);

  int offset = n*2;

  ll cnt = 0;

  ll sum = 0;

  REP(i,n) {

    v[offset] += 1;

    if (a[i] >= th) {

      offset -= 1;

      sum -= v[offset];

    } else {

      sum += v[offset];

      offset += 1;

    }

    cnt += sum;

  }

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

  ll mid = m/2 + 1;

  return cnt >= mid;

}



int main()

{

  cin.tie(0);

  std::ios::sync_with_stdio(false);

  int n;

  cin>>n;

  vecint a(n);

  REP(i,n) cin>>a[i];

  vecint b = a;

  b.push_back(0);

  b.push_back(1000000007);

  sort(ALL(b));

  b.erase(unique(ALL(b)), end(b));

  int hi = b.size()-1;

  int lo = 0;

  while ((hi - lo) > 1) {

    int mid = (hi + lo) / 2;

    if (ok(a, b[mid])) {

      hi = mid;

    } else {

      lo = mid;

    }

  }

  cout << b[lo] << endl;

  return 0;

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

#define FOR(i,k,n)  for(int i = (k);i < (n);++i)

#define REP(i,n)    FOR(i,0,n)

#define ALL(x)      begin(x),end(x)



using namespace std;

using vecint = vector<int>;

using ll = int64_t;



using Data = int;

const int len = 1 << 18;



struct BIT {

  vector<Data> data;

  BIT() : data(len, 0) {}

  void update(int i, Data value) {

    for (; i < len; i |= i+1) data[i] += value;

  }

  Data query(int i) {

    Data s = 0;

    for (; i >= 0; i = (i&i+1)-1) s += data[i];

    return s;

  }

};



bool ok(const vecint& a, const int th) {

  ll n = a.size();

  BIT bit;

  int offset = n;

  ll cnt = 0;

  REP(i,n) {

    bit.update(offset, 1);

    if (a[i] >= th) {

      offset -= 1;

    } else {

      offset += 1;

    }

    cnt += bit.query(offset-1);

  }

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

  ll mid = m/2 + 1;

  return cnt >= mid;

}



int main()

{

  int n;

  cin>>n;

  vecint a(n);

  REP(i,n) cin>>a[i];

  vecint b = a;

  b.push_back(0);

  b.push_back(1000000007);

  sort(ALL(b));

  b.erase(unique(ALL(b)), end(b));

  int hi = b.size()-1;

  int lo = 0;

  while ((hi - lo) > 1) {

    int mid = (hi + lo) / 2;

    if (ok(a, b[mid])) {

      hi = mid;

    } else {

      lo = mid;

    }

  }

  cout << b[lo] << endl;

  return 0;

}


// Faster C++ solution for the same problem (measured speedup: 3.138908004625106x):
#include <bits/stdc++.h>

#define FOR(i,k,n)  for(int i = (k);i < (n);++i)

#define REP(i,n)    FOR(i,0,n)

#define ALL(x)      begin(x),end(x)



using namespace std;

using vecint = vector<int>;

using ll = int64_t;



bool ok(const vecint& a, const int th, vecint& v) {

  ll n = a.size();

  v.assign(n*4, 0);

  int offset = n*2;

  ll cnt = 0;

  ll sum = 0;

  REP(i,n) {

    v[offset] += 1;

    if (a[i] >= th) {

      offset -= 1;

      sum -= v[offset];

    } else {

      sum += v[offset];

      offset += 1;

    }

    cnt += sum;

  }

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

  ll mid = m/2 + 1;

  return cnt >= mid;

}



int main()

{

  int n;

  scanf("%d", &n);

  vecint a(n);

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

  int hi = 1000000001;

  int lo = 0;

  vecint v(n*4);

  while ((hi - lo) > 1) {

    int mid = (hi + lo) / 2;

    if (ok(a, mid, v)) {

      hi = mid;

    } else {

      lo = mid;

    }

  }

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

  return 0;

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

#define FOR(i,k,n)  for(int i = (k);i < (n);++i)

#define REP(i,n)    FOR(i,0,n)

#define ALL(x)      begin(x),end(x)



using namespace std;

using vecint = vector<int>;

using ll = int64_t;



using Data = int;

const int len = 1 << 18;



struct BIT {

  vector<Data> data;

  BIT() : data(len, 0) {}

  void update(int i, Data value) {

    for (; i < len; i |= i+1) data[i] += value;

  }

  Data query(int i) {

    Data s = 0;

    for (; i >= 0; i = (i&i+1)-1) s += data[i];

    return s;

  }

};



bool ok(const vecint& a, const int th) {

  ll n = a.size();

  BIT bit;

  int offset = n;

  ll cnt = 0;

  REP(i,n) {

    bit.update(offset, 1);

    if (a[i] >= th) {

      offset -= 1;

    } else {

      offset += 1;

    }

    cnt += bit.query(offset-1);

  }

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

  ll mid = m/2 + 1;

  return cnt >= mid;

}



int main()

{

  int n;

  cin>>n;

  vecint a(n);

  REP(i,n) cin>>a[i];

  vecint b = a;

  b.push_back(0);

  b.push_back(1000000007);

  sort(ALL(b));

  b.erase(unique(ALL(b)), end(b));

  int hi = b.size()-1;

  int lo = 0;

  while ((hi - lo) > 1) {

    int mid = (hi + lo) / 2;

    if (ok(a, b[mid])) {

      hi = mid;

    } else {

      lo = mid;

    }

  }

  cout << b[lo] << endl;

  return 0;

}


// Faster C++ solution for the same problem (measured speedup: 3.0472104159113136x):
#include <bits/stdc++.h>

#define FOR(i,k,n)  for(int i = (k);i < (n);++i)

#define REP(i,n)    FOR(i,0,n)

#define ALL(x)      begin(x),end(x)



using namespace std;

using vecint = vector<int>;

using ll = int64_t;



bool ok(const vecint& a, const int th, vecint& v) {

  ll n = a.size();

  v.assign(n*4, 0);

  int offset = n*2;

  ll cnt = 0;

  ll sum = 0;

  REP(i,n) {

    v[offset] += 1;

    if (a[i] >= th) {

      offset -= 1;

      sum -= v[offset];

    } else {

      sum += v[offset];

      offset += 1;

    }

    cnt += sum;

  }

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

  ll mid = m/2 + 1;

  return cnt >= mid;

}



int main()

{

  cin.tie(0);

  ios::sync_with_stdio(false);

  int n;

  cin>>n;

  vecint a(n);

  string line;

  getline(cin, line);

  getline(cin, line);

  size_t pos = 0;

  REP(i,n-1) {

    const auto next = line.find(' ', pos);

    a[i] = stoi(line.substr(pos, next-pos));

    pos = next+1;

  }

  a.back() = stoi(line.substr(pos));

  int hi = 1000000001;

  int lo = 0;

  vecint v(n*4);

  while ((hi - lo) > 1) {

    int mid = (hi + lo) / 2;

    if (ok(a, mid, v)) {

      hi = mid;

    } else {

      lo = mid;

    }

  }

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

  return 0;

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

#define FOR(i,k,n)  for(int i = (k);i < (n);++i)

#define REP(i,n)    FOR(i,0,n)

#define ALL(x)      begin(x),end(x)



using namespace std;

using vecint = vector<int>;

using ll = int64_t;



using Data = int;

const int len = 1 << 18;



struct BIT {

  vector<Data> data;

  BIT() : data(len, 0) {}

  void update(int i, Data value) {

    for (; i < len; i |= i+1) data[i] += value;

  }

  Data query(int i) {

    Data s = 0;

    for (; i >= 0; i = (i&i+1)-1) s += data[i];

    return s;

  }

};



bool ok(const vecint& a, const int th) {

  ll n = a.size();

  BIT bit;

  int offset = n;

  ll cnt = 0;

  REP(i,n) {

    bit.update(offset, 1);

    if (a[i] >= th) {

      offset -= 1;

    } else {

      offset += 1;

    }

    cnt += bit.query(offset-1);

  }

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

  ll mid = m/2 + 1;

  return cnt >= mid;

}



int main()

{

  int n;

  cin>>n;

  vecint a(n);

  REP(i,n) cin>>a[i];

  vecint b = a;

  b.push_back(0);

  b.push_back(1000000007);

  sort(ALL(b));

  b.erase(unique(ALL(b)), end(b));

  int hi = b.size()-1;

  int lo = 0;

  while ((hi - lo) > 1) {

    int mid = (hi + lo) / 2;

    if (ok(a, b[mid])) {

      hi = mid;

    } else {

      lo = mid;

    }

  }

  cout << b[lo] << endl;

  return 0;

}


// Faster C++ solution for the same problem (measured speedup: 3.1373015013547816x):
#include <bits/stdc++.h>

#define FOR(i,k,n)  for(int i = (k);i < (n);++i)

#define REP(i,n)    FOR(i,0,n)

#define ALL(x)      begin(x),end(x)



using namespace std;

using vecint = vector<int>;

using ll = int64_t;



bool ok(const vecint& a, const int th, vecint& v) {

  ll n = a.size();

  v.assign(n*4, 0);

  int offset = n*2;

  ll cnt = 0;

  ll sum = 0;

  REP(i,n) {

    v[offset] += 1;

    if (a[i] >= th) {

      offset -= 1;

      sum -= v[offset];

    } else {

      sum += v[offset];

      offset += 1;

    }

    cnt += sum;

  }

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

  ll mid = m/2 + 1;

  return cnt >= mid;

}



int main()

{

  int n;

  scanf("%d", &n);

  vecint a(n);

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

  vecint b = a;

  b.push_back(0);

  b.push_back(1000000007);

  sort(ALL(b));

  b.erase(unique(ALL(b)), end(b));

  int hi = b.size() - 1;

  int lo = 0;

  vecint v(n*4);

  while ((hi - lo) > 1) {

    int mid = (hi + lo) / 2;

    if (ok(a, b[mid], v)) {

      hi = mid;

    } else {

      lo = mid;

    }

  }

  printf("%d\n", b[lo]);

  return 0;

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

#define FOR(i,k,n)  for(int i = (k);i < (n);++i)

#define REP(i,n)    FOR(i,0,n)

#define ALL(x)      begin(x),end(x)



using namespace std;

using vecint = vector<int>;

using ll = int64_t;



using Data = int;

const int len = 1 << 18;



struct BIT {

  vector<Data> data;

  BIT() : data(len, 0) {}

  void update(int i, Data value) {

    for (; i < len; i |= i+1) data[i] += value;

  }

  Data query(int i) {

    Data s = 0;

    for (; i >= 0; i = (i&i+1)-1) s += data[i];

    return s;

  }

};



bool ok(const vecint& a, const int th) {

  ll n = a.size();

  BIT bit;

  int offset = n;

  ll cnt = 0;

  REP(i,n) {

    bit.update(offset, 1);

    if (a[i] >= th) {

      offset -= 1;

    } else {

      offset += 1;

    }

    cnt += bit.query(offset-1);

  }

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

  ll mid = m/2 + 1;

  return cnt >= mid;

}



int main()

{

  int n;

  cin>>n;

  vecint a(n);

  REP(i,n) cin>>a[i];

  vecint b = a;

  b.push_back(0);

  b.push_back(1000000007);

  sort(ALL(b));

  b.erase(unique(ALL(b)), end(b));

  int hi = b.size()-1;

  int lo = 0;

  while ((hi - lo) > 1) {

    int mid = (hi + lo) / 2;

    if (ok(a, b[mid])) {

      hi = mid;

    } else {

      lo = mid;

    }

  }

  cout << b[lo] << endl;

  return 0;

}


// Faster C++ solution for the same problem (measured speedup: 3.136247496391447x):
#include <bits/stdc++.h>

#define FOR(i,k,n)  for(int i = (k);i < (n);++i)

#define REP(i,n)    FOR(i,0,n)

#define ALL(x)      begin(x),end(x)



using namespace std;

using vecint = vector<int>;

using ll = int64_t;



bool ok(const vecint& a, const int th, vecint& v) {

  ll n = a.size();

  v.assign(n*3, 0);

  int offset = n*1.5;

  ll cnt = 0;

  ll sum = 0;

  REP(i,n) {

    v[offset] += 1;

    if (a[i] >= th) {

      offset -= 1;

      sum -= v[offset];

    } else {

      sum += v[offset];

      offset += 1;

    }

    cnt += sum;

  }

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

  ll mid = m/2 + 1;

  return cnt >= mid;

}



int main()

{

  int n;

  scanf("%d", &n);

  vecint a(n);

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

  vecint b = a;

  b.push_back(0);

  b.push_back(1000000007);

  sort(ALL(b));

  b.erase(unique(ALL(b)), end(b));

  int hi = b.size() - 1;

  int lo = 0;

  vecint v(n*4);

  while ((hi - lo) > 1) {

    int mid = (hi + lo) / 2;

    if (ok(a, b[mid], v)) {

      hi = mid;

    } else {

      lo = mid;

    }

  }

  printf("%d\n", b[lo]);

  return 0;

}