stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define oo (long long)1e18

#define ll long long

#define setdp memset(dp,-1,sizeof(dp))

const ll mod = 1e9+7;

void _IOS(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);}

#define PI 3.14159265359

int n,l,r,x;

    vector<int>b(200009),a(200009);

int main()

{

    cin>>n;

    int ans=0;

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

    {

        cin>>a[i];

        if(i&1&&a[i]&1)

            ans++;

    }

    cout<<ans;

}


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



using namespace std;



int main()

{

    int counter = 0;

    int n;

    cin>>n;

    int arr[n];

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

    {

        cin>>arr[i];

        if(arr[i] % 2 !=0 && (i+1)%2 != 0)

        {

            counter++;

        }

    }

    cout<<counter;



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

using namespace std;

#define oo (long long)1e18

#define ll long long

#define setdp memset(dp,-1,sizeof(dp))

const ll mod = 1e9+7;

void _IOS(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);}

#define PI 3.14159265359

int n,l,r,x;

    vector<int>b(200009),a(200009);

int main()

{

    cin>>n;

    int ans=0;

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

    {

        cin>>a[i];

        if(i&1&&a[i]&1)

            ans++;

    }

    cout<<ans;

}


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

#include<iostream>

#include <stdio.h>

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

#define f2(j,a,b) for(int j=a; j<b; ++j)

#define F first

#define S second

#define pi 3.1415926536

#define Faast ios_base::sync_with_stdio(0);       cin.tie(0);      cout.tie(0);

#define SIZE 10

#define IN freopen("records.in","r",stdin);

const int MOD = 1e9 + 7;

const int MAX_VAL=1e6+2;

const int INF = 0x3f3f3f3f;

typedef long long ll;

using namespace std;



void file()

{

    #ifndef ONLINE_JUDGE

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

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

    #else

  // online submission

    #endif

}



int main()

{

     int n,s,cnt=0; cin>>n;

     f(i, 1, n+1) 

     { 

       cin>>s; if((i&1)&&(s&1)) cnt++;

     }

     cout<<cnt<<endl;

      return 0;

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

using namespace std;



typedef long long i64;



const int MAXN = 100000 + 5;

const int MOD = 1e9 + 7;



int N;

i64 answer, dp[MAXN];

int degree[MAXN], lenCnt[MAXN];

int pre[MAXN], nxt[MAXN];

bool vis[MAXN];



bool noSolution = false;



void findCycle()

{

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

	{

		if (degree[i] > 2)

			return noSolution = true, (void) 0;

		if (degree[i] != 2 || vis[i])

			continue;



		int cur = i;



		do

		{

			if (vis[cur])

				return noSolution = true, (void) 0;

			vis[cur] = true;

			pre[nxt[cur]] = cur;

			cur = nxt[cur];

		} while (cur != i);

	}

}



void processCircleBasedTree()

{

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

	{

		if (degree[i])

			continue;



		int cur = i, footLen = 0, cycleLen = 0;

		while (!vis[cur])

			vis[cur] = true,

			cur = nxt[cur],

			footLen++;

		do

			cur = pre[cur],

			cycleLen++;

		while (degree[cur] == 1);

		if (footLen < cycleLen)

			answer = answer * 2 % MOD;

		if (footLen > cycleLen)

			return noSolution = true, (void) 0;

	}

}



void countCycle()

{

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

	{

		if (vis[i])

			continue;

		int cur = i, len = 0;

		do

		{

			vis[cur] = true;

			cur = nxt[cur];

			len++;

		} while (cur != i);

		lenCnt[len]++;

	}

}



int main()

{

	answer = 1;

	ios::sync_with_stdio(false), cin.tie(NULL);

	cin >> N;



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

		cin >> nxt[i], degree[nxt[i]]++;



	findCycle();

	if (noSolution)

		return cout << 0 << endl, 0;

	processCircleBasedTree();

	if (noSolution)

			return cout << 0 << endl, 0;

	countCycle();

	if (noSolution)

		return cout << 0 << endl, 0;



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

	{

		dp[0] = 1LL;

		for (int j = 1; j <= lenCnt[i]; j++)

		{

			dp[j] = dp[j - 1] * (((i % 2 == 0) || i == 1) ? 1 : 2);

			if (j >= 2)

				dp[j] = (dp[j] + ((((dp[j - 2] * (j - 1)) % MOD) * i) % MOD))

						% MOD;

		}



		answer = answer * dp[lenCnt[i]] % MOD;

	}

	cout << answer << endl;

}




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

#define maxn 100005

#define mod 1000000007

int n,a[maxn],pre[maxn],deg[maxn],cnt[maxn],f[maxn],ans=1;

bool vis[maxn];

int main()

{

	scanf("%d",&n);

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

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

	{

		if(deg[i]>2) { printf("0\n"); return 0; }

		if(deg[i]<2||vis[i]) continue;

		int p=i;

		do

		{

			if(vis[p]) { printf("0\n"); return 0; }

			vis[p]=true,pre[a[p]]=p,p=a[p];

		}while(p!=i);

	}

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

		if(!deg[i])

		{

			int p=i,l1=0,l2=0;

			while(!vis[p]) vis[p]=true,p=a[p],l1++;

			do l2++,p=pre[p]; while(deg[p]!=2);

			if(l1<l2) ans=ans*2%mod;

			else if(l1>l2) { printf("0\n"); return 0; }

		}

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

		if(!vis[i])

		{

			int p=i,l=0;

			do l++,p=a[p],vis[p]=true; while(p!=i);

			cnt[l]++;

		}

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

	{

		int mul=1;

		if(i!=1&&(i&1)) mul++;

		f[0]=1,f[1]=mul;

		for(int j=2;j<=cnt[i];j++) f[j]=(1ll*f[j-2]*(j-1)%mod*i%mod+1ll*f[j-1]*mul%mod)%mod;

		ans=1ll*ans*f[cnt[i]]%mod;

	}

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

}
// 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+1)/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.4964231059352158x):
#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int N=100011;

int n,a[N],r=0,l=0,ans=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;

}

//求中位数小于等于x的区间数至少为n*(n+1)/2/2+1的最小的x 

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]-1+N);

       add(s[i]+N);

	} 

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

}

int main()

{

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

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

  scanf("%d",&n);

  l=987654321;

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

  while(l+1<=r)

  {

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

  	if(check(mid)) 

	  r=mid;

	else l=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+1)/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.5061899064244413x):
#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int N=100011;

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

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

int cc[N*10],d[N*10],tot=0;

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;

}

//求中位数小于等于x的区间数至少为n*(n+1)/2/2+1的最小的x

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]-1+N);

       add(s[i]+N);

	}  

//	cout<<x<<" "<<sum<<endl;

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

}

int main()

{

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

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

  scanf("%d",&n);  l=987654321;

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

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

//    for(int j=i;j<=n;j++)

//	  {

//	  	for(int z=1;z<=j-i+1;z++)

//	  	  cc[z]=a[i+z-1];

//	  	sort(cc+1,cc+j-i+2);

//	  	d[++tot]=cc[(j-i+1)/2+1];

//	  } 

//  sort(d+1,d+tot+1);

//  for(int i=1;i<=tot;i++) 

//    cout<<d[i]<<" ";

//  cout<<"---------"<<endl; 

//  cout<<d[tot/2+1]<<endl;

// 

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

//    check(i);

  while(l+1<=r)

  {

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

  	if(check(mid)) 

	  r=mid;

	else l=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+1)/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.4076342989331714x):
#include <cstdio>

#include <algorithm>

#include <cstring>

#include <iostream>

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

using namespace std;



inline int read() {

	int f = 1, x = 0;

	char c = getchar();

	while(c < '0' || c > '9') {

		if(c == '-')	f = -1;

		c = getchar();

	}

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

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

		c = getchar();

	}

	return x * f;

}



int n, x, a[100007], c[200007], s[100007], l, r;



inline void update(int x, int v) {

	for(; x <= 200006; x += lowbit(x))

		c[x] += v;

}

inline int sum(int x) {

	int res = 0;

	for(; x; x -= lowbit(x))

		res += c[x];

	return res;

}

inline bool check(int x) {

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

	s[0] = 0;

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

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

	long long su = 0;

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

		su += sum(s[i] + 100000);

		update(s[i] + 100000, 1);

	} 

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

}



int main() {

	n = read();

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

		a[i] = read();

		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", r);

}
// 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,ans=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: 1.1417505684728788x):
#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<math.h>

#include<algorithm>

#include<queue>

#include<set>

#include<map>

#include<iostream>

using namespace std;

#define ll long long

#define REP(a,b,c) for(int a=b;a<=c;a++)

#define re register

#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)

typedef pair<int,int> pii;

#define mp make_pair

inline int gi()

{

	int f=1,sum=0;char ch=getchar();

	while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}

	return f*sum;

}

const int N=100010;

int n,a[N],o[N],v[N],c[N<<1],s[N];

ll all;

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

void Add(int x,int d){while(x<=(n<<1)){c[x]+=d;x+=lowbit(x);}}

int query(int x){int ret=0;while(x){ret+=c[x];x-=lowbit(x);}return ret;}

bool check(int mid)

{

	for(int i=1;i<=n;i++)v[i]=(a[i]>=o[mid])?1:-1;

	ll ret=0;

	for(int i=1;i<=n;i++)s[i]=s[i-1]+v[i],ret+=(s[i]<0);

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

	for(int i=n;i;i--)

	{

		ret+=query(s[i]+n-1);

		Add(s[i]+n,1);

	}

	return ret*2<=all;

}

int main()

{

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

	for(int i=1;i<=n;i++)a[i]=o[i]=gi();sort(o+1,o+n+1);int tot=unique(o+1,o+n+1)-o-1;

	int l=1,r=tot,ans=0;

	while(l<=r)

	{

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

		if(check(mid)){ans=mid;l=mid+1;}

		else r=mid-1;

	}

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

	return 0;

}
// Slower C++ solution:
//404 Not Found {=}7 (o)7 (x)7

#include<bits/stdc++.h>

using namespace std;

#define append push_back

#define endl "\n"

#define dbug(x) cout<<#x<<"="<<x<<endl



typedef long long int ll;

typedef long double ld;

typedef pair<int,int> pii;



const ll maxn = 5e5+10, inf = 1e9, mod= 1e9+7;

ll a[maxn];

vector<ll> v;

ll b[maxn];

ll fen[maxn+10];

ll par[maxn];

ll get(ll id)

{

    ll sum = 0;

    for(;id;id -= id&-id)

        sum += fen[id];

    return sum;

}

void add(ll id)

{

    for(;id<maxn;id += id&-id)

        fen[id] ++;

}

int main(){

    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    

    ll n;

    cin >> n;

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

        cin >> a[i];

        v.append(a[i]);

    }

    sort(v.begin(),v.end());

    ll l=0,r=n;

    while(l+1 < r)

    {

        ll mid = (l+r) / 2;

        

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

            b[i] = (a[i]<v[mid]?1ll:-1ll);

        b[0] += n+2;

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

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



        ll ans = 0;

        add(n+2);

        ans += get(b[0]-1);

        add(b[0]);

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

        {

            ans += get(b[i]-1);

            add(b[i]);

        }                                   

        if(ans > (n*(n+1))/4)

        {

            r = mid;

        }

        else

        {

            l = mid;

        }

        for(ll i = 0;i<maxn;i++)

            fen[i] =0;

    }

    cout << v[l];

    

    return 0;

}

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

#include<ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;

using namespace std;

typedef long long ll;

typedef long double ld;

#define pb push_back

#define X first

#define Y second

#define sz(v) (int)v.size()

using ord = tree<int, null_type, greater<int>, rb_tree_tag, tree_order_statistics_node_update>;



void solve();



main() {

	ios_base::sync_with_stdio(0), cin.tie(0);

#ifdef ONPC

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

#endif

	int t = 1;

	//cin >> t;

	while (t--) solve();

	return 0;

}



const int N = 1e5 + 5;

int n, a[N], fenv[N + N];



void inic() {

	for (int i= 0; i < N + N; ++i) fenv[i] = 0;

}



void inc(int r, int add) {

	for (; r < N + N; r += r & -r) fenv[r] +=add;

}



int get(int r) {

	int res= 0;

	for (; r > 0; r -= r & -r) res += fenv[r];

	return res;

}



void solve() {

	cin >> n;

	for (int i = 1; i <= n; ++i) cin >> a[i];

	if (n == 1) {

		cout << a[1] << '\n';

		return;

	}

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

	int lef = 0, rig = 1e9 + 1;

	while (rig - lef > 1) {

		int mid = (lef + rig) / 2;

		ll cur = 0;

		inic();

		inc(N, 1);

		int bal = 0;

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

			int x = a[i];

			if (x >= mid) x = 1;

			else x = -1;

			bal += x;

			cur += get(N + bal);

			inc(N + bal, 1);

		}

		if (cur * 2 >= all) {

			lef = mid;

		} else {

			rig = mid;

		}

	}

	cout << lef << '\n';

}
// 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,ans=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.103612320571304x):
#include <bits/stdc++.h>



using namespace std;

#define int long long

#define x first

#define y second



#define vert int v, int tl, int tr

#define tm ((tl + tr) >> 1)

#define left (v << 1), tl, tm

#define right (v << 1) + 1, tm, tr



typedef pair<int, int> pii;

typedef long long ll;

typedef long double ld;



int n;

int a[100009];

int pref[100009];



int tree[800009];

void build(vert) {

    tree[v] = 0;

    if (tr - tl == 1) return;



    build(left);

    build(right);

}



void upd(vert, int i, int x) {

    tree[v] += x;

    if (tr - tl == 1) {

        return;

    }



    if (i < tm) {

        upd(left, i, x);

    }



    else {

        upd(right, i, x);

    }

}



int getsum(vert, int l, int r) {

    if (l >= tr || tl >= r) return 0;

    if (tl >= l && tr <= r) return tree[v];

    return getsum(left, l, r) + getsum(right, l, r);

}



int check(int x) {

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

        if (a[i] >= x)

            pref[i + 1] = pref[i] + 1;

        else

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

    }



    build(1, 0, 2 * n + 2);

    int cnt = 0;

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

        cnt += getsum(1, 0, 2 * n + 2, 0, pref[i] + n + 1);

        upd(1, 0, 2 * n + 2, pref[i] + n, 1);

    }



    return cnt;

}



signed main() {

    ios :: sync_with_stdio(0);

    cin.tie(0);



    cin >> n;

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

        cin >> a[i];

    }



    int l = 0, r = (1e9) + 1;

    int eth = (n * n) / 2;

    while (r - l > 1) {

        int m = (r + l) / 2;

        if (check(m) <= (eth + 1) / 2) {

            r = m;

        }



        else {

            l = m;

        }

    }



    cout << l;



    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<=200000;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.0997831898965886x):
#include <bits/stdc++.h>



using namespace std;

#define int long long

#define x first

#define y second



#define vert int v, int tl, int tr

#define tm ((tl + tr) >> 1)

#define left (v << 1), tl, tm

#define right (v << 1) + 1, tm, tr



typedef pair<int, int> pii;

typedef long long ll;

typedef long double ld;



int n;

int a[100009];

int pref[100009];



int tree[800009];

void build(vert) {

    tree[v] = 0;

    if (tr - tl == 1) return;



    build(left);

    build(right);

}



void upd(vert, int i, int x) {

    tree[v] += x;

    if (tr - tl == 1) {

        return;

    }



    if (i < tm) {

        upd(left, i, x);

    }



    else {

        upd(right, i, x);

    }

}



int getsum(vert, int l, int r) {

    if (l >= tr || tl >= r) return 0;

    if (tl >= l && tr <= r) return tree[v];

    return getsum(left, l, r) + getsum(right, l, r);

}



int check(int x) {

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

        if (a[i] >= x)

            pref[i + 1] = pref[i] + 1;

        else

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

    }



    build(1, 0, 2 * n + 2);

    int cnt = 0;

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

        cnt += getsum(1, 0, 2 * n + 2, 0, pref[i] + n + 1);

        upd(1, 0, 2 * n + 2, pref[i] + n, 1);

    }



    return cnt;

}



signed main() {

    ios :: sync_with_stdio(0);

    cin.tie(0);



    cin >> n;

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

        cin >> a[i];

    }



    int l = 0, r = (1e9) + 1;

    int eth = (n * n) / 2;

    while (r - l > 1) {

        int m = (r + l) / 2;

        if (check(m) <= (eth + 1) / 2) {

            r = m;

        }



        else {

            l = m;

        }

    }



    cout << l;



    return 0;

}