stablegradients/pie-gem5-pairs huggingface dataset:
// 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.120493319023582x):
#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);

  string line;

  getline(cin, line);

  getline(cin, line);

  int i = 0;

  int num = 0;

  for (char c : line) {

    if (isdigit(c)) {

      num *= 10;

      num += c - '0';

    } else {

      a[i] = num;

      ++i;

      num = 0;

    }

  }

  a[i] = num;

  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.0514932786809394x):
#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()

{

  cin.tie(0);

  ios::sync_with_stdio(false);

  int n;

  cin>>n;

  vecint a(n);

  string line;

  getline(cin, line);

  getline(cin, line);

  int i = 0;

  int num = 0;

  for (char c : line) {

    if ('0' <= c && c <= '9') {

      num *= 10;

      num += c - '0';

    } else {

      a[i] = num;

      ++i;

      num = 0;

    }

  }

  a[i] = num;

  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;

    }

  }

  cout<<b[lo]<<endl;

  return 0;

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

using namespace std;

const int N = 1e5+20;

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

long long c[N*2];

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

inline void insert(int p,long long v) { p += n+1; for (;p<=2*n+1;p+=lowbit(p)) c[p] += v; }

inline long long query(int p) { p += n+1; long long res = 0; for (;p;p-=lowbit(p)) res += c[p]; return res; }

inline void input(void)

{

    scanf("%d",&n);

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

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

}

inline long long check(int val)

{

    long long res = 0;

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

        b[i] = a[i] <= val ? 1 : -1;

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

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

    memset( c , 0 , sizeof c );

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

    {

        res += query( b[i] - 1 );

        insert( b[i] , 1 );

    }

    return res;

}

inline void BinarySearch(void)

{

    int l = 0 , r = Max , mid;

    while ( l + 1 < r )

    {

        mid = l + r >> 1;

        if ( check(mid) >= 1LL*n*(n+2)/2/2 + 1 ) r = mid;

        else l = mid;

    }

    check(l) == 1LL*n*(n+1)/2/2 + 1 ? ans = l : ans = r;

}

int main(void)

{

    input();

    BinarySearch();

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

    return 0;

}


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

#define ll long long

using namespace std;

const int N=100011;

int n,a[N],r=0,l=0;

int c[N*10],s[N<<1  ];

void add(int x)

{

	while(x<=N*2)

	  c[x]++,x+=x&(-x);

}

ll ask(int x)

{

	ll ans=0;

	while(x)

	{

		ans+=c[x];

		x-=x&(-x);

	}

	return ans;

}

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+=ask(s[i]+N);

       add(s[i]+N);

	} 

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

}

int main()

{

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

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

  scanf("%d",&n);

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

  while(l<=r)

  {

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

  	if(check(mid)) 

	  l=mid+1;

	else r=mid-1;

  }

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

  return 0;

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

#define ll long long

using namespace std;

const int N=100011;

int n,a[N],r=0,l=0;

int c[N*10],s[N<<1  ];

void add(int x)

{

	while(x<=N*2)

	  c[x]++,x+=x&(-x);

}

ll ask(int x)

{

	ll ans=0;

	while(x)

	{

		ans+=c[x];

		x-=x&(-x);

	}

	return ans;

}

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+=ask(s[i]+N);

       add(s[i]+N);

	} 

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

}

int main()

{

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

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

  scanf("%d",&n);

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

  while(l<=r)

  {

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

  	if(check(mid)) 

	  l=mid+1;

	else r=mid-1;

  }

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

  return 0;

}


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

#include <ext/pb_ds/assoc_container.hpp>

#include <ext/pb_ds/tree_policy.hpp>



using namespace __gnu_pbds;

using namespace std;





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

#define rloop(i, n) for(int i = int(n);i >= 0;i--)

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

#define SZ(c) int(c.size())

#define ALL(c) c.begin(), c.end()

#define RALL(c) c.rbegin(), c.rend()

#define PI acos(-1)

#define pb push_back

#define mp make_pair

#define fr first

#define sc second

#define sfi1(v) scanf("%d",&v)

#define sfi2(v1, v2) scanf("%d %d",&v1,&v2)

#define sfi3(v1, v2, v3) scanf("%d %d %d",&v1,&v2,&v3)

#define sfll1(v) scanf("%I64d",&v);

#define sfll2(v1, v2) scanf("%I64d %I64d",&v1,&v2)

#define sfll3(v1, v2, v3) scanf("%I64d %I64d %I64d",&v1,&v2,&v3)

#define endl '\n'



typedef vector<int> vi;

typedef vector<pair<int, int> > vii;

typedef long long ll;

typedef pair<int, int> pii;



template<typename T>

using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;





const int N = 1e5 + 5;

int arr[N];

int acc[N];

int n;



bool valid(int val) {

    range(i, 1, n) {

        if (arr[i] < val)acc[i] = -1;

        else acc[i] = 1;

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

    }



    Tree<pii> X;

    X.insert({0, 0});

    ll res = 0;

    range(i, 1, n) {

        int cnt = X.order_of_key(mp(acc[i], n + n));

        res += cnt;

        X.insert(mp(acc[i], i));

    }



    //cout << val << " " << res  << " " << (res*2 >= 1LL * n * (n + 1) / 2) << endl;

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

}



int main() {



#ifndef ONLINE_JUDGE

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

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

#endif

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    cout.tie(0);



    cin >> n;

    vi v(n);

    range(i, 1, n)cin >> arr[i], v[i - 1] = arr[i];

    sort(ALL(v));

    v.resize(unique(ALL(v)) - v.begin());



    //loop(i,SZ(v))valid(v[i]);



    int s = 0, e = SZ(v) - 1;

    while (s < e) {

        int mid = s + (e - s + 1) / 2;

        if (valid(v[mid]))

            s = mid;

        else

            e = mid - 1;

    }



    cout << v[e] << endl;





    return 0;

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

using namespace std;

const int N = 1e5+20;

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

long long c[N*2];

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

inline void insert(int p,long long v) { p += n+1; for (;p<=2*n+1;p+=lowbit(p)) c[p] += v; }

inline long long query(int p) { p += n+1; long long res = 0; for (;p;p-=lowbit(p)) res += c[p]; return res; }

inline void input(void)

{

    scanf("%d",&n);

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

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

}

inline long long check(int val)

{

    long long res = 0;

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

        b[i] = a[i] <= val ? 1 : -1;

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

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

    memset( c , 0 , sizeof c );

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

    {

        res += query( b[i] - 1 );

        insert( b[i] , 1 );

    }

    return res;

}

inline void BinarySearch(void)

{

    int l = 0 , r = Max , mid;

    while ( l + 1 < r )

    {

        mid = l + r >> 1;

        if ( check(mid) >= 1LL*n*(n+2)/2/2 + 1 ) r = mid;

        else l = mid;

    }

    check(l) == 1LL*n*(n+1)/2/2 + 1 ? ans = l : ans = r;

}

int main(void)

{

    input();

    BinarySearch();

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

    return 0;

}


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

using namespace std;

#define maxn 100005

inline void read(int& x)

{

	x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

}

int n,a[maxn],sum[maxn],c[maxn+maxn];



inline int lowbit(int x)

{

	return x&(-x);

}

inline void modify(int pos)

{

	for(int i=pos;i<=n+100000;i+=lowbit(i)) ++c[i];

}

inline int query(int pos)

{

	int ans=0;

	for(int i=pos;i;i-=lowbit(i)) ans+=c[i];

	return ans;

}



bool check(int x)

{

	sum[0]=0;

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

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

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

	long long ans=0;

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

	{

		ans+=query(sum[i]+100000);

		modify(sum[i]+100000);

	}

	return (ans<<2)>=1ll*n*(n+1);

}

int main()

{

	int l=0x3f3f3f3f,r=-0x3f3f3f3f,mid;

	read(n);

	for(int i=1;i<=n;++i) read(a[i]),l=min(l,a[i]),r=max(r,a[i]);

	while(l<=r)

	{

		mid=(l+r)>>1;

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

		else r=mid-1;

	}

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

	return 0;

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

using namespace std;

const int N = 1e5+20;

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

long long c[N*2];

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

inline void insert(int p,long long v) { p += n+1; for (;p<=2*n+1;p+=lowbit(p)) c[p] += v; }

inline long long query(int p) { p += n+1; long long res = 0; for (;p;p-=lowbit(p)) res += c[p]; return res; }

inline void input(void)

{

    scanf("%d",&n);

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

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

}

inline long long check(int val)

{

    long long res = 0;

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

        b[i] = a[i] <= val ? 1 : -1;

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

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

    memset( c , 0 , sizeof c );

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

    {

        res += query( b[i] - 1 );

        insert( b[i] , 1 );

    }

    return res;

}

inline void BinarySearch(void)

{

    int l = 0 , r = Max , mid;

    while ( l + 1 < r )

    {

        mid = l + r >> 1;

        if ( check(mid) >= 1LL*n*(n+2)/2/2 + 1 ) r = mid;

        else l = mid;

    }

    check(l) == 1LL*n*(n+1)/2/2 + 1 ? ans = l : ans = r;

}

int main(void)

{

    input();

    BinarySearch();

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

    return 0;

}


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

#include <ext/pb_ds/detail/standard_policies.hpp>

#include <ext/pb_ds/assoc_container.hpp>



using namespace std;

using namespace __gnu_pbds;



template<typename T>

using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;



template<typename T>

using normal_queue = priority_queue<T, vector<T>, greater<T>>;



#define int long long



bool check(int x, int n, vector<int>& a) {

    int cnt = 0, nw = 0;

    ordered_set<pair<int, int>> c;

    c.insert({0, 0});

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

        if (a[i] >= x) {

            nw++;

        } else {

            nw--;

        }

        cnt += c.order_of_key({nw, n + 10});

        c.insert({nw, i + 1});

    }

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

}



void solve() {

    int n;

    cin >> n;

    vector<int> a(n);

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

        cin >> a[i];

    }

    int l = -1, r = 1e9 + 10;

    while (r - l > 1) {

        //cout << l << " " << r << " >\n";

        int m = (l + r) / 2;

        if (check(m, n, a)) {

            l = m;

        } else {

            r = m;

        }

    }

    cout << l << "\n";

}



signed main() {

    ios_base::sync_with_stdio(false);

    cin.tie(0);

    int t = 1;

    //cin >> t;

    while (t--) {

        solve();

    }

    return 0;

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

#define ll long long

using namespace std;

const int N=100011;

int n,a[N],r=0,l=0;

int c[N*10],s[N<<1  ];

void add(int x)

{

	while(x<=N*2)

	  c[x]++,x+=x&(-x);

}

ll ask(int x)

{

	ll ans=0;

	while(x)

	{

		ans+=c[x];

		x-=x&(-x);

	}

	return ans;

}

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+=ask(s[i]+N);

       add(s[i]+N);

	} 

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

}

int main()

{

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

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

  scanf("%d",&n);

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

  while(l<=r)

  {

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

  	if(check(mid)) 

	  l=mid+1;

	else r=mid-1;

  }

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

  return 0;

}


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

#include <ext/pb_ds/detail/standard_policies.hpp>

#include <ext/pb_ds/assoc_container.hpp>



using namespace std;

using namespace __gnu_pbds;



template<typename T>

using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;



template<typename T>

using normal_queue = priority_queue<T, vector<T>, greater<T>>;



#define int long long



bool check(int x, int n, vector<int>& a) {

    int cnt = 0, nw = 0;

    ordered_set<pair<int, int>> c;

    c.insert({0, 0});

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

        if (a[i] >= x) {

            nw++;

        } else {

            nw--;

        }

        cnt += c.order_of_key({nw, n + 10});

        c.insert({nw, i + 1});

    }

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

}



void solve() {

    int n;

    cin >> n;

    vector<int> a(n);

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

        cin >> a[i];

    }

    int l = -1, r = 1e9 + 10;

    while (r - l > 1) {

        //cout << l << " " << r << " >\n";

        int m = (l + r) / 2;

        if (check(m, n, a)) {

            l = m;

        } else {

            r = m;

        }

    }

    cout << l << "\n";

}



signed main() {

    ios_base::sync_with_stdio(false);

    cin.tie(0);

    int t = 1;

    //cin >> t;

    while (t--) {

        solve();

    }

    return 0;

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

using namespace std;

#define maxn 100005

inline void read(int& x)

{

	x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

}

int n,a[maxn],sum[maxn],c[maxn+maxn];



inline int lowbit(int x)

{

	return x&(-x);

}

inline void modify(int pos)

{

	for(int i=pos;i<=n+100000;i+=lowbit(i)) ++c[i];

}

inline int query(int pos)

{

	int ans=0;

	for(int i=pos;i;i-=lowbit(i)) ans+=c[i];

	return ans;

}



bool check(int x)

{

	sum[0]=0;

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

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

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

	long long ans=0;

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

	{

		ans+=query(sum[i]+100000);

		modify(sum[i]+100000);

	}

	return (ans<<2)>=1ll*n*(n+1);

}

int main()

{

	int l=0x3f3f3f3f,r=-0x3f3f3f3f,mid;

	read(n);

	for(int i=1;i<=n;++i) read(a[i]),l=min(l,a[i]),r=max(r,a[i]);

	while(l<=r)

	{

		mid=(l+r)>>1;

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

		else r=mid-1;

	}

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

	return 0;

}

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

#include <ext/pb_ds/detail/standard_policies.hpp>

#include <ext/pb_ds/assoc_container.hpp>



using namespace std;

using namespace __gnu_pbds;



template<typename T>

using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;



template<typename T>

using normal_queue = priority_queue<T, vector<T>, greater<T>>;



#define int long long



bool check(int x, int n, vector<int>& a) {

    int cnt = 0, nw = 0;

    ordered_set<pair<int, int>> c;

    c.insert({0, 0});

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

        if (a[i] >= x) {

            nw++;

        } else {

            nw--;

        }

        cnt += c.order_of_key({nw, n + 10});

        c.insert({nw, i + 1});

    }

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

}



void solve() {

    int n;

    cin >> n;

    vector<int> a(n);

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

        cin >> a[i];

    }

    int l = -1, r = 1e9 + 10;

    while (r - l > 1) {

        //cout << l << " " << r << " >\n";

        int m = (l + r) / 2;

        if (check(m, n, a)) {

            l = m;

        } else {

            r = m;

        }

    }

    cout << l << "\n";

}



signed main() {

    ios_base::sync_with_stdio(false);

    cin.tie(0);

    int t = 1;

    //cin >> t;

    while (t--) {

        solve();

    }

    return 0;

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

using namespace std;

const int N = 1e5 + 87;

const int M = N * 2;

int n,a[N],f[M];

void add(int i)

{

    for (; i < M; i += i & -i)

        ++f[i];

}

int qry(int i)

{

    int r=0;

    for (; i ; i ^= i & -i)

        r += f[i];

    return r;

}

bool ok(int k)

{

    memset(f,0,sizeof(f));

    int s = N;

    add(s);

    long long t = (n * (n + 1LL) / 2 + 1) / 2;

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

        s += a[i] >= k ? 1 : -1;

        t -= qry(s);

        add(s);

    }

    return t <= 0;

}

int main()

{

    ios::sync_with_stdio(0);

    cin.tie(0);

    cin >> n;

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

        cin >> a[i];

    int lo = 1, hi = 1e9;

    while (lo <= hi) {

        int mi = (lo + hi) / 2;

        if (ok(mi))

            lo = mi + 1;

        else

            hi = mi - 1;

    }

    cout << hi << '\n';

}


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

using namespace std;

const int N = 1e5 + 87;

const int M = N * 2;

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

void add(int i)

{

    for (; i < M; i += i & -i)

        ++f[i];

}

int qry(int i)

{

    int r=0;

    for (; i ; i ^= i & -i)

        r += f[i];

    return r;

}

bool ok(int k)

{

    memset(f,0,sizeof(f));

    int s = N;

    add(s);

    long long t = (n * (n + 1LL) / 2 + 1) / 2;

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

        s += a[i] >= k ? 1 : -1;

        t -= qry(s);

        add(s);

    }

    return t <= 0;

}

int main()

{

    ios::sync_with_stdio(0);

    cin.tie(0);

    cin >> n;

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

        cin >> a[i];

    copy_n(a+1,n,b);

    sort(b,b+n);

    int bn = unique(b,b+n) - b, ans = 0;

    for (int k = 1<<__lg(bn); k; k >>= 1)

        if ((ans | k) < bn && ok(b[ans | k]))

            ans |= k;

    cout << b[ans] << '\n';

}