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

#define ll long long int

#define M 1000000007

#define mod 998244353

#define mp(x,y) make_pair(x,y)

#define pb(x) push_back(x)

#define pi pair<ll,ll>

using namespace std;

const ll N=1e5+10;



ll n,k;

ll ar[N];

ll dp[N];



ll func(ll i)

{

    if(i>=n){return(INT_MAX);}

    if(i==n-1){return(0);}

    if(dp[i]==-1)

    {

        ll ans=INT_MAX;

        for(ll j=0;j<k;++j)

        {

            ans=min(ans,func(i+j+1)+abs(ar[i]-ar[i+j+1]));

        }

        dp[i]=ans;

    }

    return(dp[i]);

}



int main()

{

	ios_base::sync_with_stdio(false);

	cin.tie(NULL);

	cout.tie(NULL);



	//freopen("input.txt","r",stdin);

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



	cin>>n>>k;

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

    {

        cin>>ar[i];

    }

    memset(dp,-1,sizeof(dp));

    cout<<func(0);



	return(0);

}


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

#define ll long long int

#define M 1000000007

#define mod 998244353

#define mp(x,y) make_pair(x,y)

#define pb(x) push_back(x)

#define pi pair<ll,ll>

using namespace std;

const ll N=100010;



vector<ll> ar;

ll k;

ll dp[N];

ll func(ll idx)

{

    if(idx<0){return INT_MAX;}

    if(idx==0){return 0;}

    if(dp[idx]==-1)

    {

        ll ans=INT_MAX;

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

        {

            if(idx-i>=0)

            {ans=min(ans,func(idx-i)+abs(ar[idx]-ar[idx-i]));}

        }

        dp[idx]=ans;

    }

    return dp[idx];

}



int main()

{

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    cout.tie(NULL);



    ll n;

    cin>>n>>k;

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

    {

        ll x;

        cin>>x;

        ar.pb(x);

        dp[i]=-1;

    }



    ll ans=func(n-1);



    cout<<ans<<endl;



    return (0);

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

#include <ext/numeric>



using namespace std;

using namespace __gnu_cxx;



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

#define endl "\n"

#define pb push_back

#define F first

#define S second

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

#define isOdd(n)    (n&1)

#define LLMAX LLONG_MAX

#define LLMIN LLONG_MIN

#define IMN INT_MIN

#define IMX INT_MAX

#define pow(n, m) power((ll)n, (ll)m)

#define numOfDigits(n)  ((n)? (ll)(log10(n)+1) : 1)

#define mem(x, val)    memset(x, val, sizeof(x))



typedef long long ll;

typedef long double ld;

typedef double dd;

typedef string str;

typedef pair<int, int> pii;





vector<int> v;

int dp[(int)1e5];

int n, k;

int jump(int i){

    if(i==n-1) return 0;

    if(i>=n) return 1e9;



    int &ret = dp[i];



    if(~ret) return ret;



    int cnt = 1e9;

    for(int j = 1; j<=k; j++){

        if(i+j<n) cnt = min(cnt, abs(v[i] - v[i+j]) + jump(i+j));

    }



    return ret = cnt;

}

int main()

{

    THINK_TWICE_CODE_ONCE

    //freopen("test cases\\.txt", "r", stdin) ;

    cin>>n>>k;

    v.resize(n);

    for(int &i: v) cin>>i;

    mem(dp, -1);

    cout<<jump(0);

    return 0;

}










// Faster C++ solution for the same problem (measured speedup: 1.3952327840177248x):
#define _CRT_SECURE_NO_WARNINGS

#include<iostream>

#include<functional>

#include <bitset>

#include<algorithm>

#include<fstream>

#include<string>

#include <cstring>

#include<stdio.h>

#include<iomanip>

#include<sstream>

#include<cmath>

#include<vector>

#include<assert.h>

#include<queue>

#include<deque>

#include<stack>

#include<set>

#include<map>

// never lose hope ..

typedef unsigned long long ull;

typedef long long ll;

typedef long double ld;

#define eps 1e-8

using namespace std;

double const  PI = 3.141592653;

const int OO = 1000000000 + 9;



void fast() {

	ios_base::sync_with_stdio(0);

	cin.tie(NULL), cout.tie(NULL);

}





int main()

{

	fast();



	int n, k;

	cin >> n >> k;

	vector<int>v(n + 1, 0), dp(n + 1, OO);

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

		cin >> v[i];

	}

	dp[1] = 0;

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

		for (int j = 1;j <= min(i, k);j++) {

			dp[i] = min(dp[i], dp[i - j] + abs(v[i] - v[i - j]));

		}

	}

	cout << dp[n];





	return 0;

}
// Slower C++ solution:
#include<iostream> 

#include<cstring>

using namespace std;

const int maxn=1e5+10;

const int inf=0x3f3f3f3f;

int main()

{

	int a[maxn]; 

	int dp[maxn];

	int n,k;

	cin>>n>>k;

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

	 cin>>a[i];

	memset(dp,0x3f,sizeof(dp));

	dp[1]=0;

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

		for(int j=1;j<=k;j++)

		{

			if(i-j<1)

				break;

			dp[i]=min(dp[i],dp[i-j]+(abs(a[i]-a[i-j])));

		}			

	cout<<dp[n]<<endl;

	return 0;

}

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

using namespace std;

const int maxn=100010;

const int inf=0x3f3f3f3f;

int dp[maxn];

int a[maxn];

int main()

{

	int n,k;

	cin>>n>>k;

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

	for(int i=2;i<=n;i++)dp[i]=inf;

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

		for(int j=1;j<=k;j++) {

			if(i-j<1)break;

			dp[i]=min(dp[i],dp[i-j]+abs(a[i]-a[i-j]));

		}

	}

	cout<<dp[n];

}
// Slower C++ solution:
#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

int res[100005] = {0};

int N,d = 0;

long long sum = 0;

int main()

{



     while(~scanf("%d",&N))

    {

     sum = 0;

     memset(res,0,sizeof(res));

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

     {

        scanf("%d",&d);

        res[d] ++;

        sum+= d;

     }

     int Q;

     scanf("%d",&Q);

     int y=0,x=0;

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

        scanf("%d %d",&y,&x);

        sum += (x-y)*res[y];

        res[x] += res[y];

        res[y] = 0;

        cout<<sum<<endl;

     }

     }

    return 0;

}


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

using namespace std;

typedef long long ll;

int main()

{

	ll n,q,ans=0,a,b,c;

	cin>>n;

	map<ll,ll>m;

	while (n--)

	{

		cin>>a;

		ans+=a;

		m[a]++;

	}

	cin>>q;

	while (q--)

	{

		cin>>b>>c;

		ans+=m[b]*(c-b);

		m[c]+=m[b];

		m[b]=0;

		cout<<ans<<"\n";

	}

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

 

#define ull unsigned long long

#define ll long long

#define pb push_back

#define mp make_pair

#define y1 my_y1

#define fi first

#define se second

#define lcm mylcm

 

using namespace std;

 

const ll mod = 998244353;

const ll inf = 2e9;

const int N = 1e5 + 5;



ll n, h[N], dp[N], k;



int main () {

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

    cin.tie(NULL);

	cout.tie(NULL);

	ios_base::sync_with_stdio(false);

	cin >> n >> k;

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

		cin >> h[i];

		dp[i] = inf;

	}

	dp[1] = 0;

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

		for (int j = 1; j <= k; j++) {

			if (i - j > 0) dp[i] = min(dp[i - j] + abs(h[i - j] - h[i]), dp[i]);

		}

	}

	cout << dp[n];

	return 0;

}

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

#include <cstring>



using namespace std;



const int maxn = 1e5+5;

int n,K;

int h[maxn],f[maxn];



int abs(int x,int y) {

	if (x - y < 0) return y - x;

	return x - y;

}



int min(int x,int y) {

	if (x < y) return x;

	return y;

}



int main() {

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

	scanf("%d %d",&n,&K);

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

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

	}

	f[0] = f[1] = 0;

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

		for (int k = 1; k <= K && k < i; k++){

			f[i] = min(f[i-k]+abs(h[i],h[i-k]),f[i]);

		}

	}

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

	return 0;

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

using namespace std;

#define db(x) cerr<<__LINE__<<": "<<#x<<" = "<<(x)<<'\n'

const int N = 1e6;

const int inf = 1e9;



int main(){

	ios_base::sync_with_stdio(0);

	int a,b,n,k,T,cas=0;

	cin>>n>>k;

	vector<int> A(n);

	for(int &x: A) {

		cin>>x;

	}

	vector<int> dp(n, inf);

	dp[0]=0;

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

		for(int j=i+1, cnt=1;j<n && cnt<=k;++j,++cnt) {

			dp[j] = min(dp[j], dp[i] + abs(A[j]-A[i]));

		}

	}

	cout<<dp[n-1]<<endl;

	return 0;

}

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

#include <cstring>



using namespace std;



const int maxn = 1e5+5;

int n,K;

int h[maxn],f[maxn];



int abs(int x,int y) {

	if (x - y < 0) return y - x;

	return x - y;

}



int min(int x,int y) {

	if (x < y) return x;

	return y;

}



int main() {

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

	scanf("%d %d",&n,&K);

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

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

	}

	f[0] = f[1] = 0;

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

		for (int k = 1; k <= K && k < i; k++){

			f[i] = min(f[i-k]+abs(h[i],h[i-k]),f[i]);

		}

	}

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

	return 0;

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

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

#define ll long long

#define ld long double

using namespace std;

const ll  mod = 1000000007;





int solve(int n, int m, int counter){

	//base case

	if (n == m) return counter;

	if (m < n) return counter + (n - m);



	//sol steps

	if (m % 2 == 0)

		return solve(n, m / 2, counter + 1);

	return solve(n, m + 1, counter + 1);

}



int main()

{

	H

	int n, k;

	cin >> n >> k;

	int arr[n + 1];

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

		cin >> arr[i];

	}

	int dp[n + 1];

	memset(dp, 0x3f3f3f3f, sizeof dp);

	dp[0] = dp[1] = 0;

	dp[2] = abs(arr[1] - arr[2]);

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

		for (int j = 1; i - j > 0 && j <= k; j++){

			dp[i] = min(dp[i], dp[i - j] + abs(arr[i] - arr[i - j]));

		}

	}

	cout << dp[n];

	return 0 ;

}


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

#include<stdlib.h>

#include<math.h>





typedef long long ll;





ll *mem, *inp, dist, min_dist, N;

int k;



int main()

{

    ll i, j;

    scanf("%lld%d", &N, &k);



    mem =(ll*) malloc(N * sizeof(ll));

    inp =(ll*) malloc(N * sizeof(ll));



    for(i = 0; i<N; ++i){

        scanf("%lld", inp+i);

    }



    *(mem+N-2) = llabs(*(inp+N-2) - *(inp+N-1));



    for(i = 3; i<=k+1 && i<=N; ++i)

        *(mem+N-i) = llabs(*(inp+N-i) - *(inp+N-1));



    for(i = N-(k+2); i>=0; --i){



        min_dist = llabs(*(inp+i) - *(inp+i+1)) + *(mem+i+1);

        for(j = 2; j<=k && i+j<N; ++j){

            dist = llabs(*(inp+i) - *(inp+i+j)) + *(mem+i+j);

            if (dist < min_dist) min_dist = dist;

        }



        *(mem+i) = min_dist;

    }



    printf("%lld\n", *mem);



    return 0;

}
// Slower C++ solution:
#include<iostream>

#include<utility>

#include<climits>



typedef std::pair<int, int> P;



const int MAX_N = 1 << 17;



int n;

// fst: -得点, snd: チームの番号

P dat[MAX_N * 2 - 1];



int cnt[MAX_N];



void init( int n_ )

{

	n = 1;

	while( n < n_ )

		n *= 2;



	for( int i = 0; i != n * 2 - 1; ++i )

		dat[i] = std::make_pair( INT_MAX, INT_MAX );



	return;

}



void update( int k, P x )

{

	k += n - 1;

	dat[k] = x;

	while( k > 0 )

	{

		k = (k - 1) / 2;

		dat[k] = std::min( dat[k*2+1], dat[k*2+2] );

	}



	return;

}



// [a,b)

P query( int a, int b, int k, int l, int r )

{

	if( a >= r || b <= l )

		return std::make_pair( INT_MAX, INT_MAX );

	

	if( a <= l && r <= b )

		return dat[k];

	else

	{

		P vl = query( a, b, k * 2 + 1, l, (l + r) / 2 );

		P vr = query( a, b, k * 2 + 2, (l + r) / 2, r );

		

		return std::min( vl, vr );

	}

}



int main()

{

	int N, R, L;

	std::cin >> N >> R >> L;



	init( N );

	for( int i = 0; i != N; ++i )

		update( i, std::make_pair( 0, i ) );



	int prevT = 0;

	for( int i = 0; i != R; ++i )

	{

		int d, t, x;

		std::cin >> d >> t >> x;



		--d;



		if( t != prevT )

		{

			P p = query( 0, N, 0, 0, n );

			cnt[p.second] += t - prevT;

		}



		P p = query( d, d + 1, 0, 0, n );

		update( d, std::make_pair( p.first - x, p.second ) );



		prevT = t;

	}



	if( prevT != L )

	{

		P p = query( 0, N, 0, 0, n );

		cnt[p.second] += L - prevT;

	}



	int t = -1, id;

	for( int i = 0; i != N; ++i )

	{

		if( t < cnt[i] )

		{

			t = cnt[i];

			id = i + 1;

		}

	}

	

	std::cout << id << std::endl;



	return 0;

}

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

#include<algorithm>

#include<utility>

#define rep(i,a) for( int i = 0; i != (a); ++i )



typedef std::pair<int, int> P;



const int MAX_N = 1 << 17, INF = 1 << 30;



int sz;

P dat[2*MAX_N-1];



void init( int n )

{

	sz = 1;

	while( sz < n )

		sz <<= 1;



	rep( i, 2*sz-1 )

		dat[i] = P( INF, INF );



	return;

}



void update( int k, P p )

{

	k += sz-1;

	dat[k] = p;



	while( k > 0 )

	{

		k = (k-1)>>1;

		dat[k] = std::min( dat[2*k+1], dat[2*k+2] );

	}



	return;

}



P query( int a, int b, int k, int l, int r )

{

	if( b <= l || r <= a )

		return P( INF, INF );



	if( a <= l && r <= b )

		return dat[k];

	else

		return std::min( query( a, b, 2*k+1, l, (l+r)>>1 ), query( a, b, 2*k+2, (l+r)>>1, r ) );

}



int N, R, L;

int cnt[MAX_N];



int main()

{

	scanf( "%d%d%d", &N, &R, &L );



	init( N );

	rep( i, N )

		update( i, P( 0, i ) );

	

	int prvT = 0;

	rep( i, R )

	{

		int d, t, x;

		scanf( "%d%d%d", &d, &t, &x );



		if( prvT != t )

			cnt[query( 0, N, 0, 0, sz ).second] += t - prvT;



		--d;

		P p = query( d, d+1, 0, 0, sz );

		update( d, P( p.first - x, p.second ) );

		prvT = t;

	}



	if( L != prvT )	

		cnt[query( 0, N, 0, 0, sz ).second] += L - prvT;

	

	printf( "%d\n", std::max_element( cnt, cnt+N )-cnt+1 );



	return 0;

}
// Slower C++ solution:
#include <iostream>

#include <algorithm>

#include <cmath>

#include <cstdlib>

#include <cstdio>

#include <cstring>

#include <iomanip>

#include <string>

#include <set>

#include <vector>

#include <queue>

#include <stack>

using namespace std;

#define ms(a, x) memset(a, x, sizeof(a))

#define fore(i, a, n) for (long long i = a; i < n; i++)

#define ford(i, a, n) for (long long i = n - 1; i >= a; i--)

#define si(a) scanf("%d", &a)

#define sii(a, b) scanf("%d%d", &a, &b)

#define debug(a) cout << a << endl

#define endl '\n'

#define pi acos(-1.0)

#define tr t[root]

#define lson t[root << 1]

#define rson t[root << 1 | 1]

#define IO ios::sync_with_stdio(false), cin.tie(0)

const double eps = 1e-8;

inline int sgn(const double &x) { return x < -eps ? -1 : x > eps; }

typedef long long ll;

const int inf = 0x3f3f3f3f;

const int maxn=100500;



//=================================================

int a[maxn];

int dp[maxn];

int n,k;

void init() {

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

        if(i==1) {

            dp[i]=0;

        }

        else  {

            dp[i]=inf;

        }

    }

}

int main()

{

    IO;

    cin>>n>>k;

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

        cin>>a[i];

    }

    init();

    if(k>=n-1) {

        cout<<abs(a[n]-a[1])<<endl;

    }

    else {

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

            int minn=min(i-1,k);

            for(int j=1;j<=minn;j++)

            dp[i]=min(dp[i],dp[i-j]+abs(a[i]-a[i-j]));

        }

        cout<<dp[n]<<endl;

    }

    



    return 0;

}

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

#include <cstring>



using namespace std;



const int maxn = 1e5+5;

int n,K;

int h[maxn],f[maxn];



int abs(int x,int y) {

	if (x - y < 0) return y - x;

	return x - y;

}



int min(int x,int y) {

	if (x < y) return x;

	return y;

}



int main() {

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

	scanf("%d %d",&n,&K);

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

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

	}

	f[0] = f[1] = 0;

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

		for (int k = 1; k <= K && k < i; k++){

			f[i] = min(f[i-k]+abs(h[i],h[i-k]),f[i]);

		}

	}

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

	return 0;

}
// Slower C++ solution:
//Inbornhandsome

#include <bits/stdc++.h>

using namespace std;

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

#define FIO freopen("input.txt","r",stdin); freopen("output.txt","w",stdout)

#define endl '\n'

#define int long long



const int N = 1e5 + 7;



int stones[N], cost[N], n, k;



int find_cost(int stone)

{

    if(stone > n)   return 1e9;

    if(stone == n)  return 0;



    int &ans = cost[stone];



    if(ans != -1) return ans;



    ans = 1e10;



    for(int i = 1; i <= k and stone + i <= n; ++ i)

    {

        ans = min(ans, abs(stones[stone] - stones[stone + i]) + find_cost(stone + i));

    }

    

    

    return ans;

}



int32_t main()

{

    IOS; //FIO;



    cin >> n >> k;



    memset(cost,-1,sizeof(cost));



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

        cin  >> stones[i];



    cout << find_cost(1);



    return 0;

}

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

using namespace std;



#define endl '\n'

#define int long long



const int N = 1e5+9;

int cache[N], h[N], n, k;



int32_t main()

{

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



	cin >> n >> k;

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

		cin >> h[i];

	}

	for(int i = n-1; i > 0; i --) {

		cache[i] = 1e9;

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

			cache[i] = min(cache[i], abs(h[i]-h[i+j])+cache[i+j]);

		}

	}

	cout << cache[1] << endl;



	return 0;

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

using namespace std;

typedef long long ll;

const int maxn=1e5+10;

ll n,a[maxn],tree[maxn*2],pre[maxn*2],l,r;

void add(int x,ll v){

	for(int i=x;i<=2*maxn;i+=i&-i)

    	tree[i]+=v;

}

ll ask(int x){

    ll ans=0;

    for(int i=x;i>0;i-=i&-i)

    	ans+=tree[i];

    return ans;

}

bool check(int mid){

	memset(tree,0,sizeof(tree));

	pre[0]=0;

	ll ans=0;

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

		pre[i]=pre[i-1]+(a[i]>=mid?1:-1);

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

		ans+=ask(pre[i]+maxn); 

		add(pre[i]+maxn,1);

	}

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

}

int main(){

	cin>>n;

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

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

    }

    cout<<r;

	return 0;

} 


// Faster C++ solution for the same problem (measured speedup: 3.361675919698669x):
#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);

}
// Slower C++ solution:
#include<iostream>

using namespace std;



int A[100005];



int partition(int p, int r) {

    int x = A[r];

    int i = p - 1;

    for (int j=p; j<r; j++) {

        if (A[j] <= x) {

            i++;

            swap(A[i], A[j]);

        }

    }

    swap(A[i+1], A[r]);

    return i + 1;

}



int main() {

    int n;

    cin >> n;

    for (int i=0; i<n; i++) cin >> A[i];

    int idx = partition(0, n-1);

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

        if (i == idx) cout << "[";

        cout << A[i];

        if (i == idx) cout << "]";

        cout << (i != n-1 ? " " : "\n");

    }

}


// Faster C++ solution for the same problem (measured speedup: 5.129690493529547x):
/*

#include<iostream>

using namespace std;



int A[100005];



int partition(int p, int r) {

    int x = A[r];

    int i = p - 1;

    for (int j=p; j<r; j++) {

        if (A[j] <= x) {

            i++;

            swap(A[i], A[j]);

        }

    }

    swap(A[i+1], A[r]);

    return i + 1;

}



int main() {

    int n;

    cin >> n;

    for (int i=0; i<n; i++) cin >> A[i];

    int idx = partition(0, n-1);

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

        if (i == idx) cout << "[";

        cout << A[i];

        if (i == idx) cout << "]";

        cout << (i != n-1 ? " " : "\n");

    }

}

*/



#include<stdio.h>

#define MAX 100000



int A[MAX], n;



int partition(int p, int r) {

    int x, i, j, t;

    x = A[r];

    i = p - 1;

    for (j = p; j < r; j++) {

        if (A[j] <= x) {

            i++;

            t = A[i]; A[i] = A[j]; A[j] = t;

        }

    }

    t = A[i + 1]; A[i + 1] = A[r]; A[r] = t;

    return i + 1;

}



int main() {

    int i, q;



    scanf("%d", &n);

    for (i = 0; i < n; i++) scanf("%d", &A[i]);



    q = partition(0, n - 1);



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

        if (i) printf(" ");

        if (i == q) printf("[");

        printf("%d", A[i]);

        if (i == q) printf("]");

    }

    printf("\n");



    return 0;

}
// Slower C++ solution:
/*

Code By RyeCatcher

*/

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cctype>

#include <iostream>

#include <algorithm>

#include <ext/pb_ds/hash_policy.hpp>

#include <ext/pb_ds/assoc_container.hpp>

#include <queue>

#define ri register int 

#define ll long long 

#define ull unsigned long long 

using std::min;

using std::max;

using std::lower_bound;

using namespace __gnu_pbds;

template <class T>inline void read(T &x){

    x=0;int ne=0;char c;

    while(!isdigit(c=getchar()))ne=c=='-';

    x=c-48;

    while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;

    x=ne?-x:x;return ;

}

const int maxn=200005;

const int inf=0x7fffffff;

int n,nn,a[maxn],b[maxn],c[maxn],mx=-inf,mi=inf;

ll sum[maxn<<2];

inline void update(int x,int d){for(;x<=nn;x+=x&(-x))sum[x]+=d;}

inline ll query(int x){ll ans=0;for(;x;x-=x&(-x))ans+=sum[x];return ans;}

inline ll chk(int k){

    ll ans=0;

    b[0]=0;

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

        b[i]=b[i-1]+((a[i]<=k)?1:-1);

        c[i]=b[i];

        ans+=(b[i]>0);

    }

    std::sort(c+1,c+1+n);

    nn=std::unique(c+1,c+1+n)-(c+1);

    memset(sum,0,sizeof(sum));

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

    	b[i]=lower_bound(c+1,c+1+nn,b[i])-c;

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

        update(b[i],1);

    }

    return ans;

}

int main(){

    read(n);

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

        read(a[i]);

        mi=min(mi,a[i]),mx=max(mx,a[i]);

    }

    int L=mi,R=mx,mid,ans;

	ll lim=1ll*n*(n+1)/4+1;//注意long long 

    while(L<=R){

        mid=(L+R)>>1;

        if(chk(mid)>=lim)ans=mid,R=mid-1;

        else L=mid+1;

    }

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

    return 0;

}

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

#define ll long long

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

#define swap(x,y) (x^=y^=x^=y)

inline int read()

{

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

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

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

	return x*f;

}

#define MN 100005 

int n,m,a[MN],b[MN],c[MN];

int t[MN<<1];

void C(int x){for(;x<MN*2;x+=(x&-x))t[x]++;}

int G(int x){int res=0;for(;x;x-=(x&-x))res+=t[x];return res;}

inline bool check(int x)

{

	ll cnt=0ll;

	register int i;

	for(i=1;i<=n;++i) c[i]=c[i-1]+(a[i]>=x?1:-1);

	memset(t,0,sizeof t);

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

	{

		C(c[i-1]+MN);

		cnt+=G(c[i]+MN);

	}

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

}

int main()

{

	n=read();register int i;

	for(i=1;i<=n;++i) a[i]=b[i]=read();

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

	m=std::unique(b+1,b+n+1)-b-1;

	int l,r,ans;

	for(l=1,r=m,ans=0;l<=r;)

	{

		int mid=l+r>>1;

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

		else r=mid-1;

	}

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

}