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

#define ll long long

using namespace std;



ll n;

std::vector<ll> ara(100010);

ll dp[100010];

ll k;



ll fnc(ll i){

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

  if(i >= n)return 1<<30;

  if(dp[i] != -1)return dp[i];

  ll res1 = 1<<30;

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

    res1 = min(res1, abs(ara[i]-ara[i+j]) + fnc(i+j));

  }

  dp[i] = res1;

  return dp[i];

}



int main(int argc, char const *argv[]) {

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

  cin >> n >> k;

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

    cin >> ara[i];

  }

  cout << fnc(0) << endl;



  return 0;

}


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

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

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

#define     bug(a,b)        cout<<a<<"\t"<<b<<"\n";

#define     Case(a,b)       cout<<"Case "<<a<<": "<<b<<"\n";

#define     watch(a)        cout<<fixed<<setprecision(a)

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

#define     Endl            "\n";

#define     tab             "\t"

#define     reset(a,b)      memset(a,b,sizeof(a));

#define     sf(a)           scanf(" %d", &a);

#define     srt(a)          sort(a.begin(),a.end());

#define     pi              2*acos(0.0)

#define     inf             INT_MAX

const int sz=1e5+9;

int n,x,arr[sz],dp[sz],k;



int clac(int i){

    if(i==n) return 0;

    if(dp[i]!=-1)return dp[i];

    int ret1=inf;

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

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

    }

    return dp[i]=ret1;

}



void solve(){

    cin>>n>>k;

    reset(dp,-1);

    lp(i,1,n+1)cin>>arr[i];

    cout<<clac(1)<<"\n";

}



int main(){

    //FasterIO;

    #ifndef ONLINE_JUDGE

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

    #endif

    // int t;

    //cin>>t;

    //while(t--)

        solve();

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

#include<string.h>

#include<time.h>

#include<math.h>

#include<stdlib.h>

#include<iostream>

#include<iomanip>

#include<utility>

#include<algorithm>

#include<stack>

#include<queue>

#include<map>

#include<set>

#define ll long long

#define fi first

#define sec second

#define pb push_back

#define mp make_pair

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

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



const double PI=acos(-1);

const double EPS=1e-12;

const int MOD=1e9+7;

const int INF=1<<30;





using namespace std;



int dat[100005];

int minn[100005];



int main(){

	int in;

	int t,k,min_k;

	cin>>in>>k;

	rep(i,in,1){

		cin>>dat[i];

	}

	for(int i=in-1;i>=1;i--){

		t=INF;

		min_k=min(k,in-i);

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

			t=min(t,abs(dat[i]-dat[i+j])+minn[i+j]);

		}

		minn[i]=t;

	}

	cout<<minn[1]<<endl;	

	return 0;

}

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

using namespace std;

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

#define MOD(a) (a>0?a:-(a))

#define custoate(i)

int main(){

  int npedras, maxpulo;

  scanf("%d %d",&npedras,&maxpulo);

  int hpedra[npedras],custoate[npedras];

  for (size_t i = 0; i < npedras; i++)

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

  custoate[0] = 0;

  int tempcost = 2147483647,k,tempcost2;

  for (size_t i = 1; i < npedras; i++,tempcost = 2147483647) {

    // printf("i = %d, tempcost = %d\n", i,tempcost);

    for (k= (maxpulo>i ? i : maxpulo); k > 0; k--) {

      // printf("k = %d ",k);

      tempcost2 = custoate[i-k] + MOD(hpedra[i-k]-hpedra[i]);

      if (tempcost > tempcost2)

        tempcost = tempcost2;

    }

    // printf("custo[%d] = %d",i,tempcost);

    custoate[i] = tempcost;

    // printf("\n\n");

  }

  printf("%d\n", custoate[npedras-1]);



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

#include <set>

#include <stack>

#include <vector>

#include <map>

#include <string>

#include <string.h>

#include <cstring>

#include <queue>

#include <algorithm>

#include <math.h>



using namespace std;



typedef long long ll;



int N, K;

int stonez[100001];

int DP[100001];



int calculate(int index) 

{

	if (index == N - 1)

		return DP[index] = 0;



	if (DP[index] != -1)

		return DP[index];



	int ans = abs(stonez[index] - stonez[index+1]) + calculate(index+1);

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

	{

		if(index + i < N)

			ans = min(ans, abs(stonez[index] - stonez[index + i]) + calculate(index + i));

	}

	return DP[index] = ans;

}



int main()

{

	cin >> N >> K;

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

	{

		cin >> stonez[i];

	}

	memset(DP,-1,sizeof DP);

	cout << calculate(0);

}

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

 

using namespace std;

 

#define mp make_pair

#define fi first

#define se second

#define pb push_back

typedef long long ll ;

typedef long double ld ;

typedef pair<ll, ll> pairs;

 

 

ll h[100009] ;

ll v[100009] ;

 

int main()

{

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

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

    ios_base::sync_with_stdio(0);

    cin.tie(NULL);

    cout.tie(NULL);

 

    ll n , k ; cin >> n >> k ;

    for ( ll i = 0 ; i < n ; i++ ) cin >> h[i] ;

    for ( ll i = 1 ; i < min( n , k ) ; i++ ) v[i] = abs( h[i] - h[0] ) ;

    for ( ll i = k ; i < n  ; i++ ){ v[i] = 1000000009 ;

        for ( ll j = i - k; j < i ; j++ ){

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

            //cout << x << " " << y << " " << v[x] <<  "\n\n" ;

        }

    }  cout << v[n-1] ;

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

#include <cstdint>

#include <cstdio>

#include <iostream>



const int kMaxN = 200000;

const int kMaxAi = 1000000000;

const int kSentinel = kMaxAi + 1;



void Merge(int A[], int left, int mid, int right,

           int L[], int R[], std::int64_t *cnt) {

  int i, j, k;

  int n1 = mid - left;

  int n2 = right - mid;

  for (i = 0; i < n1; ++i) { L[i] = A[left + i]; }

  for (i = 0; i < n2; ++i) { R[i] = A[mid + i]; }

  L[n1] = R[n2] = kSentinel;

  i = j = 0;

  for (k = left; k < right; ++k) {

    if (L[i] <= R[j]) {

      A[k] = L[i++];

    } else {

      A[k] = R[j++];

      *cnt += n1 - i;

    }

  }

}



void MergeSort(int A[], int left, int right,

               int L[], int R[], std::int64_t *cnt) {

  int mid;

  if (left + 1 < right) {

    mid = (left + right) / 2;

    MergeSort(A, left, mid, L, R, cnt);

    MergeSort(A, mid, right, L, R, cnt);

    Merge(A, left, mid, right, L, R, cnt);

  }

}



int main() {

  int n, i;

  std::scanf("%d", &n);

  int A[n];

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

  int L[n/2 + 1], R[n/2 + 1];

  std::int64_t cnt = 0;

  MergeSort(A, 0, n, L, R, &cnt);

  std::cout << cnt << std::endl;

}

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

#include <cstdint>

#include <cstdio>



const int kMaxN = 200000;

const int kMaxAi = 1000000000;

const int kSentinel = kMaxAi + 1;



void Merge(int A[], int left, int mid, int right,

           int L[], int R[], std::int64_t *cnt) {

  int i, j, k;

  int n1 = mid - left;

  int n2 = right - mid;

  for (i = 0; i < n1; ++i) { L[i] = A[left + i]; }

  for (i = 0; i < n2; ++i) { R[i] = A[mid + i]; }

  L[n1] = R[n2] = kSentinel;

  i = j = 0;

  for (k = left; k < right; ++k) {

    if (L[i] <= R[j]) {

      A[k] = L[i++];

    } else {

      A[k] = R[j++];

      *cnt += n1 - i;

    }

  }

}



void MergeSort(int A[], int left, int right,

               int L[], int R[], std::int64_t *cnt) {

  int mid;

  if (left + 1 < right) {

    mid = (left + right) / 2;

    MergeSort(A, left, mid, L, R, cnt);

    MergeSort(A, mid, right, L, R, cnt);

    Merge(A, left, mid, right, L, R, cnt);

  }

}



int main() {

  int n, i;

  std::scanf("%d", &n);

  int A[n];

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

  int L[n/2 + 1], R[n/2 + 1];

  std::int64_t cnt = 0;

  MergeSort(A, 0, n, L, R, &cnt);

  std::printf("%" PRId64 "\n", cnt);

}
// Slower C++ solution:
// Author : Mohamed Sameh

#include<iostream>

#include<vector>

#include<map>

#include<set>

#include<algorithm>

#include<cmath>

#include<queue>

#include<list>

#include<stack>

#include<deque>

#include <cstring>

#include <iomanip>    

using namespace std ;

typedef long long ll ;



#define pb push_back

#define f first

#define s second

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

#define rall(v) v.rbegin(),v.rend()

#define PI  3.141592 

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

void READ (string INPUT = "NO" , string OUTPUT = "NO" )

{

    if (INPUT != "NO")

    freopen(INPUT.c_str() , "r" , stdin );

    if (OUTPUT!="NO")

    freopen ( OUTPUT.c_str() , "w" , stdout);

} 

int n ,k ; 

int a[100001]; 

int dp[100001]; 

int solve (int i)

{

    if (i==n-1)

        return 0 ; 

    if (i >= n)

        return 2e9 ; 

    if (dp[i]!=-1)return dp[i]; 

    int &ret = dp[i];ret = 2e9 ;  

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

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

    

    return ret ; 

}

int main ()

{

    memset (dp,-1,sizeof dp );

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

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

        scanf ("%d" , a+i); 

    printf ("%d\n" , solve(0)); 

    return 0 ; 

}

// Faster C++ solution for the same problem (measured speedup: 1.4089338709580776x):
// Author : Mohamed Sameh

#include <bits/stdc++.h>

typedef long long ll ;

#define pb push_back

#define f first

#define s second

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

#define rall(v) v.rbegin(),v.rend()

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

#define Flush fflush(stdout);

using namespace std ;

const int M = 1e5 ;

int n , k ;

int a[M];

int dp[M];

int main()

{

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

    for (int i =0 ; i < n ;i++)scanf ("%d" ,a+i );

    dp[1] = abs(a[0] - a[1]);

    dp[0] = 0 ;

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

    {

        dp[i] = dp[i-1] + abs (a[i] - a[i-1]);

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

        {

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

        }

    }

    printf ("%d\n" , dp[n-1]);

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



using namespace std;



#define INF (1ll << 62)

#define pb push_back

#define ii pair<int,int>

#define OK cerr <<"OK"<< endl

#define debug(x) cerr << #x " = " << (x) << endl

#define ff first

#define ss second

#define int long long

#define tt tuple<int, int, int>

#define endl '\n'



signed main () {

  

  ios_base::sync_with_stdio(false);

  cin.tie(NULL);



  int n, k;



  cin >> n >> k;



  vector<int> dp(n + 1);

  vector<int> arr(n + 1);



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

  	cin >> arr[i];

  }



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

  	dp[i] = INF;

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

  		if(i - j >= 1) {

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

  		} else {

  			break;

  		}

  	}

  }



  cout << dp[n] << endl;

}


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

using namespace std;

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

#define MOD(a) (a>0?a:-(a))

#define custoate(i)

int main(){

  int npedras, maxpulo;

  scanf("%d %d",&npedras,&maxpulo);

  int hpedra[npedras],custoate[npedras];

  for (size_t i = 0; i < npedras; i++)

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

  custoate[0] = 0;

  int tempcost = 2147483647,k,tempcost2;

  for (size_t i = 1; i < npedras; i++,tempcost = 2147483647) {

    // printf("i = %d, tempcost = %d\n", i,tempcost);

    for (k= (maxpulo>i ? i : maxpulo); k > 0; k--) {

      // printf("k = %d ",k);

      tempcost2 = custoate[i-k] + MOD(hpedra[i-k]-hpedra[i]);

      if (tempcost > tempcost2)

        tempcost = tempcost2;

    }

    // printf("custo[%d] = %d",i,tempcost);

    custoate[i] = tempcost;

    // printf("\n\n");

  }

  printf("%d\n", custoate[npedras-1]);



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

using namespace std;



#define pb push_back

#define mp make_pair

#define fi first

#define se second

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

#define rall(x) (x).rbegin(), (x).rend()

#define MAX 1000000

//3

typedef long long ll;

typedef pair<int,int> pii;

priority_queue< int > pq;

priority_queue< int , vector<int> , greater<int> > rpq;

set<int>s;

set <int > :: iterator itr; 

vector<int> vec[1001];

int r,n,m,inp,tc;

int arr[1000007]= {};

map<int , int> mymap;





int main()

{

	int n,h;

	cin>>n>>h;

	

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

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

	}

	

	for(int i=0 ;i<h-1 ; i++)

	arr[i] = arr[h-1];

	

	int dp[1000007]= {0};

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

	dp[i] = 0;

	

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

		dp[i] = INT_MAX;

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

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

		}

	}

	cout<<dp[n+(h-2)]<<endl;

    return 0;

}



//65 900 17 13

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

using namespace std;

typedef long long LL;



int arr[100007];

int dp[100007];



int Solve(int idx, int n, int k){

//	cout<<cost<<" "<<idx<<endl;

	if(idx >= n)return 1e9;

	if(idx == n - 1){

		return 0;	

	}

	

	if(dp[idx] != -1)return dp[idx];

	

	int ans = 1e9;

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

		ans = min(ans, abs(arr[idx] - arr[idx+i]) + Solve(idx+i, n, k));

	}

	

	return dp[idx] = ans;

}



int main(){

	int n, k; cin>>n>>k;

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

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

		

	cout<<Solve(0,n,k)<<endl;

	return 0;

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

  using namespace std ;



 int main(){

   int k,i;

   string s;

   cin>>k;

   cin>>s;

    if(s.size()<=k){

        cout<<s<<endl;

    }

    else{

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

        cout<<s[i];

    }

    cout<<"...";

    }







  return 0;

 }


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

#include<string.h>

int main(){

	int k;

	char s[105];

	scanf("%d",&k);

	getchar();

	scanf("%s",&s);

	if(strlen(s)>k){

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

			printf("%c",s[i]);

		}

		printf("...");

		printf("\n");

	}

	else{

		int l = strlen(s);

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

			printf("%c",s[i]);

		printf("\n");

	}

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

#include <cstring>

#include <algorithm>

#include <cmath>

#define N 100006

#define ll long long

#define dd double

#define esp 1e-10

using namespace std;



int n,m;

int num[N];



int main(){

	ll ans=0;

	int t1,t2;

	memset(num,0,sizeof(num));

	scanf("%d",&n);

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

		scanf("%d",&t1);

		ans+=t1;

		++num[t1];

	}

	scanf("%d",&m);

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

		scanf("%d%d",&t1,&t2);

		num[t2]+=num[t1];

		ans+=(t2-t1)*num[t1];

		num[t1]=0;

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

	}

}

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



using namespace std;

const int Maxn = 1e5 + 10;

int a[Maxn], n,q;

int main() {

//#define LOCAL

#ifdef LOCAL

    freopen("/Users/ttjy/Desktop/in.txt", "r", stdin);

#endif

    cin >> n;

    int ai;

    long long sum = 0;

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

        scanf("%d", &ai);

        a[ai]++;

        sum += ai;

    }

    cin >> q;

    while (q--) {

        int b, c;

        scanf("%d%d", &b, &c);

        sum +=a[b]* c-a[b]* b;

        a[c] += a[b];

        a[b] = 0;



        cout << sum << endl;

    }

    return 0;

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

#include <algorithm>



using namespace std;



int N, A, B, used[100], rings[100], G[100][199];



int rec(int pos)

{

	int ret = 1; used[pos] = 1;



	for(int i = 0; i < rings[pos]; i++)

	{

		if(!used[G[pos][i]])

		{

			ret = max(ret, rec(G[pos][i]) + 1);

		}

	}



	used[pos] = 0;



	return ret;

}



int main()

{

	int N, A, B;



	while(true)

	{

		scanf("%d", &N);

 

		if(N == 0) { break; }



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

		{

			used[i] = 0; rings[i] = 0;

		}



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

		{

			scanf("%d", &A); A--;

			scanf("%d", &B); B--;



			G[A][rings[A]] = B; rings[A]++;

			G[B][rings[B]] = A; rings[B]++;

		}



		int nodes = 0;



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

		{

			if(rings[i])

			{

				nodes++;

			}

		}



		int ret = 0;



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

		{

			ret = max(ret, rec(i));



 			if(ret == nodes) break;

		}

 

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

	}



	return 0;

}

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

#include <algorithm>

#pragma warning(disable : 4996)

using namespace std;

int N, A, B, v[100], r[100], G[100][199];

int rec(int pos) {

	int ret = 0; v[pos] = 1;

	for (int i = 0; i < r[pos]; i++) {

		if (!v[G[pos][i]]) ret = max(ret, rec(G[pos][i]));

	}

	v[pos] = 0;

	return ret + 1;

}

int main() {

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

		for (int i = 0; i < 100; i++) r[i] = 0;

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

			scanf("%d%d", &A, &B), A--, B--;

			G[A][r[A]++] = B, G[B][r[B]++] = A;

		}

		int ret = 0;

		for (int i = 0; i < 100; i++) ret = max(ret, rec(i));

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

	}

	return 0;

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



using namespace std;

using namespace std;

typedef long long ll;

#define endl "\n";

#define MAX 10000001+9   //Maximum array size;

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

#define loop2(n) for(ll i=0;i<n;i+=2)

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

#define sz(v)  v.size()

typedef vector<ll> vi;

typedef set<ll> si;



void fast() {



    cin.tie(0);

    cin.sync_with_stdio(0);

}



int pow(int a, int b) {

    int pow = 1;

    loop(b)pow *= a;

    return pow;

    //thanks m7md :)

}



int main() {

    fast();

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

    int n,k,counter=0;cin>>n>>k;

    int c[n];

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

        cin>>c[i];

        if(c[i]>=k)counter++;

    }

    cout<<counter;

}




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



int main ()

{

	long long int N,K,c=0,i,h[100000]; 

	scanf("%lld%lld",&N,&K);

	

	

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

	{

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

		if(h[i]>=K)

		{

			c++;

		}

	}

	printf("%lld\n",c);

	return 0;

	

}
// Slower C++ solution:
// In the name of God



#include <bits/stdc++.h>



using namespace std;



int main() {

	ios_base::sync_with_stdio(false);

	cin.tie(0);



	int k;

	cin >> k;

	

	string s;

	cin >> s;



	cout << s.substr(0, min(k, (int)s.length()));



	if(s.length() > k) cout << "...";



	return 0;

}


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



int main(){

	int k;

	char word[100];

	scanf("%d", &k);

	scanf("%s", &word);

	

	int len = 0;

	

	for(int i = 0; word[i] != '\0'; i++){

		len++;

	}

	

	if(len <= k){

		printf("%s\n", word);

	}

	else{

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

			printf("%c", word[i]);

		}

		printf("...\n");

	}

	return 0;

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

#include <cstdio>

#include <cstring>

#include <algorithm>

#define ll long long

#define lowbit(a) a&(-a)

#define INF 0x3f3f3f3f

using namespace std;



inline int read(){

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

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

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

	return f*sum;

}



const int N=100001;

ll n,a[N];ll s[N];

ll c[N],tot;ll t[(N<<1)+5];



inline ll ask(int x){

	ll ret=0;

	for(int i=x;i;i-=lowbit(i)) ret+=t[i];

	return ret;

}



inline void add(int x,int k){

	for(int i=x;i<=(N<<1);i+=lowbit(i)) t[i]+=k;

}



inline bool check(int mid){

	memset(t,0,sizeof(t));s[0]=0;ll sum=0;

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

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

		sum+=ask(s[i]+N);add(s[i]+N,1);

	}

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

}



int main(){

	n=read();

	for(int i=1;i<=n;i++) a[i]=read(),c[i]=a[i];

	sort(c+1,c+n+1);int m=unique(c+1,c+n+1)-c-1;

	for(int i=1;i<=n;i++) a[i]=lower_bound(c+1,c+m+1,a[i])-c;

	int l=1,r=n;

	while(l<=r){

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

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

		else r=mid-1;

	}

	printf("%lld\n",c[r]);

	return 0;

}


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

#define int long long

using namespace std;

int a[1000001],n,ans;

int s[1000001],c[5000001];

int lowbit(int x)

{

	return x&(-x);

}

void add(int x,int d)

{

	for (;x<=n*4;x+=lowbit(x))

		c[x]+=d;

	return;

}

int sum(int x)

{

	ans=0;

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

		ans+=c[x];

	return ans;

}

bool check(int x)

{

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

		c[i]=0;

	s[0]=0;

	int res=0;

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

	{

		if (a[i]>=x)

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

		else

			s[i]=s[i-1]-1;

	}

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

	{

		res+=sum(s[i]+n+1);

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

	}

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

}

signed main()

{

	int first,last,mid,ans=-(1e+9),minn=1e+9,maxn=-(1e+9);

	cin>>n;

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

	{

		cin>>a[i];

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

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

	}

	first=minn;

	last=maxn;

	ans=minn;

	while (first<=last)

	{

		mid=(first+last)/2;

		if (check(mid))

		{

			ans=max(ans,mid);

			first=mid+1;

		}

		else

			last=mid-1;

	}

	cout<<ans<<endl;

	return 0;

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

#include <assert.h>

#include <stdlib.h>

#include <time.h>

#include <stdio.h>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <stack>

#include <string>

#include <string.h>

#include <cmath>

#include <algorithm>

#include <iomanip>

using namespace std;



const int N = 1e5 + 2;



int n, k, h[N];

long long dp[N];



long long calc(int i)

{

    if (i == n - 1)

    {

        return 0;

    }

    long long &ret = dp[i];

    if (ret != -1)

    {

        return ret;

    }

    ret = 1e9;

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

    {

        if (i + j >= n)

        {

            break;

        }

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

    }

    return ret;

}



int main()

{

    memset(dp, -1, sizeof dp);

    cin >> n >> k;

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

    {

        cin >> h[i];

    }

    cout << calc(0) << endl;

    return 0;

}

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

#include <assert.h>

#include <stdlib.h>

#include <time.h>

#include <stdio.h>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <stack>

#include <string>

#include <string.h>

#include <cmath>

#include <algorithm>

#include <iomanip>

#define ll long long

using namespace std;



const int N = 1e5 + 7;

const long long oo = 1e18L + 5;



int n, k;



int main() {

    cin >> n >> k;

    vector<int> h(n + 1);

    vector<ll> dp(n + 2, oo);

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

        cin >> h[i];

    }

    dp[0] = 0;

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

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

            if (i + j >= n) {

                break;

            }

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

        }

    }

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

    return 0;

}