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

#include <ext/pb_ds/assoc_container.hpp>

#define fastio() ios_base::sync_with_stdio(false);

#define rmod(x, y) ((((x)%(y))+(y))%(y))

using namespace std;

using namespace __gnu_pbds;

typedef long long ll;

typedef long double ld;

template<typename T, typename R = null_type, typename C = less<T>>

tree<T, R, C, rb_tree_tag, tree_order_statistics_node_update> ordered_set(){

	return tree<T, R, C, rb_tree_tag, tree_order_statistics_node_update>();

}



const ll inf = 1e17;

const int maxn = 17, maxm = (1<<16)+5;

bool vis[maxn][maxm];

int n;

ll a[maxn][maxn], val[maxm], dp[maxm];



ll solve(int mask){

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

	ll ret = -inf;

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

		ret = max(ret, val[i]+solve(mask^i));

	}

	return dp[mask] = ret;

}





int main(){

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

	scanf("%d", &n);

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

		for(int j = 0; j<n; j++) scanf("%lld", &a[i][j]);

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

		if(__builtin_popcount(i) <= 1) val[i] = 0, dp[i] = 0;

		else for(int j = 0; j<n; j++) if ((i>>j)&1){

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

				if ((i>>k)&1) val[i]+=a[j][k];

		}

	}

	printf("%lld\n", solve((1<<n)-1));

	

	return 0;

}


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

#define ull unsigned long long

#define ll long long

#define endl '\n'

#define pb push_back

#define mod 1000000007

#define mp make_pair

#define pi acos(-1)

#define line cout<<"----------------------------"<<endl

#define fast ios_base::sync_with_stdio(false); cin.tie(NULL)

#define filein freopen("input.txt","r",stdin)

#define fileout freopen("output.txt","w",stdout)

using namespace std;

const ll  mx=3009;

ll pre[1LL<<17]; 

int ara[17][17]; 

ll dp[1<<17] ; 

int main()

{

	fast; 

	int  n;

	cin>>n; 

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

	{

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

	}

	for(int mask=0;mask<(1<<n);mask++)

	{

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

		{

			if(mask&(1<<j))

			{

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

				{

					if(mask&(1<<k))

					{

						pre[mask]+=ara[j][k]; 

					}

				}

			}

		}

	}

	

	for(int mask=0;mask<(1<<n);mask++)

	{

		dp[mask]=pre[mask]; 

		for(int i=mask;i;i=(i-1)&mask)

		{

			dp[mask]=max(dp[mask],dp[mask^i]+pre[i]);

		}

	}

	cout<<dp[(1LL<<n)-1]<<endl;

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

using namespace std;



#define INF 1e9



typedef vector <int> vi;



int main() {

    int n, k;

    cin >> n >> k;



    int v[n];

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



    vi dp(n, INF);

	dp[0] = 0;



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

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

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

		}

    }



	// for (int i = 0; i < n; i++) cout << dp[i] << " ";

	// cout << endl;



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

}


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

#include<algorithm>



int main(){

  int s,k;

  long long st[100001],p[100001];

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

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

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

  }

  p[0]=0;

  p[1]=0;

  p[2]=(st[2]-st[1] < 0) ? st[1]-st[2] : st[2]-st[1];

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

    p[i] = 1000000001;

  }

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

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

      if(i-j>=1){

	long long tmp;

	tmp = (st[i]-st[i-j] < 0) ? st[i-j]-st[i] : st[i]-st[i-j];

	if(p[i] > p[i-j]+tmp){

	  p[i] = p[i-j]+tmp;

	}

	if(tmp == 0) break;

      }else{

	break;

      }

    }

  }

  printf("%lld\n",p[s]);

  return 0;

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

#define fr(i,a,n) for(ll i=a;i<n;i++)

#define YES cout<<"YES"<<endl

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

#define NO cout<<"NO"<<endl

#define pb(x) emplace_back(x)

#define fastio std::ios_base:: sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define vi vector<ll>

#define mi map<ll,ll>

#define pi pair<ll,ll>

#define what(x) cout<<#x<<" ="<<x<<endl;

#define scn(n) scanf("%d",&n)

#define print(a) printf("%d",a);

using namespace std;

using ll =int;

ll n;



ll dp[200005],a[200005]={1000000000};

ll invalid=1e9,k;

ll cnt=0;

int solve(ll i,ll p)

{ //cnt++;

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

    if(i>=n)return 1e9;

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

    //what(p-a[i]);

    //cout<<i<<" GG "<<i+1<<endl;

    ll ans=1e9,x;

    fr(l,1,min(k,n)+1){

        //what(l);

    x=abs(a[i+l]-a[i])+solve( i+l,a[i]);



    ans=min(x,ans);



    }







    return dp[i]=ans;



}



int main()

{

    ll t;

    memset(dp,-1,sizeof dp);



    scn(n);

    scn(k);

    fr(i,0,n)cin>>a[i];



    solve(0,a[0]);



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

    //what(cnt);

    //fr(i,0,n)cout<<dp[i]<<" ";



}




















































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

typedef long long ll;

using namespace std;

ll dp[100005];

int main()

{

   ll n,k;

   cin>>n>>k;

   ll a[n];

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

    cin>>a[i];

    dp[i]=1000000000;

   }

   dp[n-1]=0;

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

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

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

   }

   }

   cout<<dp[0];

    return 0;

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

#include <unordered_map>

#include <vector>

#include <stack>

#include <algorithm>

#include <list>

#include <set>

#include <climits>

#include <cmath>

#define lli long long int

using namespace std ;



int eval(vector<int> &height, vector<int> &dp, int i, int k)

{

	if(i == 0) return 0 ;

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



	dp[i] = INT_MAX ;



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

	{

		if(i-j < 0) break ;

		dp[i] = min(dp[i], eval(height,dp,i-j,k) + abs(height[i] - height[i-j])) ;

	}



	return dp[i] ;

}



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

{

	int n,k ;

	cin>>n>>k ;



	vector<int> height(n) ;

	vector<int> dp(n,-1) ;

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



	cout<<eval(height,dp,n-1,k)<<endl ;

	return 0;

}


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

#include<algorithm>



int main(){

  int s,k;

  long long st[100001],p[100001];

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

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

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

  }

  p[0]=0;

  p[1]=0;

  p[2]=(st[2]-st[1] < 0) ? st[1]-st[2] : st[2]-st[1];

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

    p[i] = 1000000001;

  }

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

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

      if(i-j>=1){

	long long tmp;

	tmp = (st[i]-st[i-j] < 0) ? st[i-j]-st[i] : st[i]-st[i-j];

	if(p[i] > p[i-j]+tmp){

	  p[i] = p[i-j]+tmp;

	}

	if(tmp == 0) break;

      }else{

	break;

      }

    }

  }

  printf("%lld\n",p[s]);

  return 0;

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



#define for0(i, n) for (long long  i = 0; i < n; i++) 

#define for1(i, n) for (long long  i = 1; i <= n; i++) 

#define forc(i, l, r) for (long long  i = l; i <= r; ++i) 

#define forr0(i, n) for (long long  i = n - 1; i >= 0; i--) 

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



#define pb push_back

#define fi first

#define se second



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

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



using namespace std;



typedef vector<int> vi;

typedef vector<vi> vvi;

typedef pair<int, int> ii;

typedef vector<ii> vii;

typedef long long ll;

typedef long long int lli;

typedef vector<ll> vll;

typedef vector<vll> vvll;

typedef double ld;



const ll N = 1e5 + 105;

const ll mod = 1e9 + 7;



int main() 

{

    ios_base::sync_with_stdio(0);

    cin.tie(0); cout.tie(0);

    

    ll i,j,k,n;

    cin>>n>>k;

    vector<ll> a(N);

    vector<ll> dp(N,INT_MAX);

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

    for0(i,N) dp[i]=1e15;

    dp[0]=0;

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

    {

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

        {

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

        }

    }

    // for0(i,n) cout<<dp[i]<<" ";

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

    

    return 0;

}




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

 

#define for0(i, n) for (long long  i = 0; i < n; i++) 

#define for1(i, n) for (long long  i = 1; i <= n; i++) 

#define forc(i, l, r) for (long long  i = l; i <= r; ++i) 

#define forr0(i, n) for (long long  i = n - 1; i >= 0; i--) 

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

 

#define pb push_back

#define fi first

#define se second

 

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

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

 

using namespace std;

 

typedef vector<int> vi;

typedef vector<vi> vvi;

typedef pair<int, int> ii;

typedef vector<ii> vii;

typedef long long ll;

typedef long long int lli;

typedef vector<ll> vll;

typedef vector<vll> vvll;

typedef double ld;

 

const ll N = 1e5 + 115;

const ll mod = 1e9 + 7;

 

int main() 

{

    ios_base::sync_with_stdio(0);

    cin.tie(0); cout.tie(0);

    

    ll i,j,k,n;

    cin>>n>>k;

    ll a[N],dp[N];

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

    for0(i,N) dp[i]=1e15;

    dp[0]=0;

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

    {

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

        {

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

        }

    }

    // for0(i,n) cout<<dp[i]<<" ";

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

    

    return 0;

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

using namespace std;



#define rep(i,x,y) for(int i=(x);i<(y);++i)

#define mp(a,b) make_pair((a),(b))

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

 

#ifdef DEBUG

#define _GLIBCXX_DEBUG

#define dump(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl

#else

#define dump(x)

#endif



typedef long long int ll;

typedef pair<int,int> pii;

//template<typename T> using vec=std::vector<T>;



const int INF=1<<30;

const long long int INFLL=1LL<<58;

const double EPS=1e-9;

const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};



template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){

	os << "[";

	for (const auto &v : vec) {

		os << v << ",";

	}

	os << "]";

	return os;

}



void solve(){

    string a,b;

    cin >> a >> b;

    

    static int dp[1001][1001];

    fill_n((int*)dp,1001*1001,INF);



    rep(i,0,a.size()+1) dp[i][0]=i;

    rep(j,0,b.size()+1) dp[0][j]=j;



    rep(i,1,a.size()+1){

        rep(j,1,b.size()+1){

            int cost=!(a[i-1]==b[j-1]);

            dp[i][j]=min({dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+cost});

        }

    }

    

    cout << dp[a.size()][b.size()] << endl;

}



int main(){

	std::ios::sync_with_stdio(false);

	std::cin.tie(0);

	solve();

	return 0;

}

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

using namespace std;



#define rep(i,x,y) for(int i=(x);i<(y);++i)

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



#ifdef DEBUG

#define _GLIBCXX_DEBUG

#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl

#else

#define print(x)

#endif



const int inf=1e9;

const int64_t inf64=1e18;

const double eps=1e-9;



template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){

    os << "[";

    for (const auto &v : vec) {

    	os << v << ",";

    }

    os << "]";

    return os;

}



int levenshtein_distance(const std::string &s,const std::string &t){

    std::vector<std::vector<int>> dp(s.size()+1,vector<int>(t.size()+1,s.size()+t.size()));

    for(int i=0; i<s.size(); ++i) dp[i][0]=i;

    for(int i=0; i<t.size(); ++i) dp[0][i]=i;

    for(int i=1; i<=s.size(); ++i){

        for(int j=1; j<=t.size(); ++j){

            int cost=s[i-1]==t[j-1]?0:1;

            dp[i][j]=min(dp[i-1][j-1]+cost,min(dp[i-1][j],dp[i][j-1])+1);

        }

    }

    return dp[s.size()][t.size()];

}



void solve(){

    string s1,s2;

    cin >> s1 >> s2;

    cout << levenshtein_distance(s1,s2) << endl;

}



int main(){

    std::cin.tie(0);

    std::ios::sync_with_stdio(false);

    cout.setf(ios::fixed);

    cout.precision(10);

    solve();

    return 0;

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

#include<algorithm>

#include<vector>

#include<cmath>

using namespace std;

int n,m,xx[10005],yy[10005],ff[10005];

double ans;

struct pt

{

	int a,b;

	double ds;	

}c;

bool cmp(pt r,pt s)

{

	return r.ds>s.ds;

}

int ft(int x)

{

	if(ff[x]==x) return x;

	return ff[x]=ft(ff[x]);

}

vector<pt>p;

int main()

{

	int i;

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

	for(i=1;i<=n;i++) { scanf("%d%d",&xx[i],&yy[i]);ff[i]=i;}

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

	{

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

		c.ds=sqrt((xx[c.a]-xx[c.b])*(xx[c.a]-xx[c.b])+(yy[c.a]-yy[c.b])*(yy[c.a]-yy[c.b])+0.0);

		p.push_back(c);

	}

	sort(p.begin(),p.end(),cmp);

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

		if(ft(p[i].a)!=ft(p[i].b)) ff[ft(p[i].b)]=ft(p[i].a);

		else ans+=p[i].ds;

	printf("%.3f\n",ans);

}

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

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;



struct node

{

    int x,y,id;

};

struct edge

{

    int u,v;

    double cost;

    edge() {}

    edge(int x,int y,double z)

    {

        u=x;

        v=y;

        cost=z;

    }

    bool operator <(const edge& a) const

    {

        return cost>a.cost;

    }

};



edge es[50010];

int par[10010];

node p[10010];

int n,m;

void init()

{

    for(int i=1;i<=n;i++) par[i]=i;

}



int find(int x)

{

    return x==par[x]?x:par[x]=find(par[x]);

}



void unite(int x,int y)

{

    x=find(x);

    y=find(y);

    if(x!=y) par[x]=y;

}



double dis(int a,int b)

{

    return sqrt(1.0*(p[a].x-p[b].x)*(p[a].x-p[b].x)+1.0*(p[a].y-p[b].y)*(p[a].y-p[b].y));

}



double kruskal()

{

    sort(es,es+m);

    //for(int i=0;i<m;i++) printf("%d %d %lf\n",es[i].u,es[i].v,es[i].cost);

    double s=0;

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

    {

        edge e=es[i];

        if(find(e.u)!=find(e.v))

        {

            unite(e.u,e.v);

        }

        else

        {

            s+=e.cost;

        }

    }

    return s;

}

int main()

{

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

    int a,b;

    double c,sum;

    while(~scanf("%d%d",&n,&m))

    {

        init();

        sum=0;

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

        {

            scanf("%d%d",&p[i].x,&p[i].y);

        }

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

        {

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

            c=dis(a,b);

            es[i]=edge(a,b,c);

        }

        printf("%.3lf\n",kruskal());

    }

    return 0;

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

using namespace std;

typedef long long int ll;

vector<int> memo(1000000, INT_MAX);

void solve(){

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

	vector<int> a(n);

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

	{

		cin>>a[i];

	}



	memo[0] = 0;

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

	{

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

			if(j<n){

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

			}

		}

	}

	cout<<memo[n-1]<<"\n";

}

int main(){

    ios_base::sync_with_stdio(false);

    cin.tie(nullptr);

    // ll t; cin>>t;

    // while(t--)

    solve();

    return 0;

}


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

using namespace std;

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

#define  ll  long long

int main()

{

    ft

    ll t,i,j,n,m,l,r;

    cin>>n>>m;

    ll a[n+2],d[n+2];

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

    {

        cin>>a[i];

    }

    d[1]=0;

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

    {

        d[i]=LLONG_MAX;

        for(j=1;j<=m;j++)

        {

            if((i-j)>0)

            {

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

            }

        }

    }

    cout<<d[n]<<"\n";

    return 0;

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

using namespace std;

using ll = long long;

using ii = pair<int, int>;

using iii = pair<ii, int>;

#define vt vector

#define pq priority_queue

#define pb push_back

#define pf push_front

#define mp make_pair

#define fi first

#define se second

#define __lcm(a, b) a * b / __gcd(a, b)

const int MOD = 1e9 + 7;

const int INF = 2e9;

const int N = 1e5 + 5;



int n, k;

int a[N], dp[N];



int f(int idx) {

    if(idx == n) return 0;

    int &sol = dp[idx];

    if(sol != -1) return sol;

    sol = INF;

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

        if(idx + i <= n)

            sol = min(sol, f(idx + i) + abs(a[idx] - a[idx + i]));

    }

    return sol;

}



void solve() {

    cin >> n >> k;

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

        cin >> a[i];

    }

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

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

}



int main() {

 

    ios_base::sync_with_stdio(0);

    cin.tie(0); cout.tie(0);

    

    solve();

    

}

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

using namespace std;

#define LL  long long

#define LIM 100000

#define mx  1000000007



int dp[LIM+5], vis[LIM+5];

int n, k, ara[LIM+5];



int f(int pos){

    if(pos == n) return 0;

    if(pos > n) mx;

    if(vis[pos]) return dp[pos];

    vis[pos] = 1;



    int mn = mx;

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

        if(pos+i > n) break;

        mn = min(mn, abs(ara[pos]-ara[pos+i]) + f(pos+i));

    }

    return dp[pos] = mn;

}



int main(){

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

    for(int i = 1; i <= n; i++) scanf("%d", ara+i);

    int res = f(1);



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

}
// Slower C++ solution:
/*D - ... (Triple Dots)*/



#include <bits/stdc++.h>

using namespace std;



int main(){



	ios_base::sync_with_stdio(0);

	cin.tie(0);

	cout.tie(0);



	int k;

	string cad;

	

	cin >> k >> cad;



	int tam = cad.size();



	if(tam > k){



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

			cout << cad[i];

		

		cout << "...";

	}

	else

		cout << cad;



	return 0;

}

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



int main(){

  int k, len = 0;

  scanf("%d", &k);

  char str[100];

  scanf("%s", str);

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

    len++;

  }

  if(len <= k){

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

  }

  else{

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

      if(i < k + 3){

        str[i] = '.';

      }

      else{

        str[i] = '\0';

      }

    }

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

  }

  return 0;

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

using namespace std;

long long dif(long long a, long long b)

{

    long long ans=a-b;

    if(ans<0) ans*=-1;

    return ans;

}

int main()

{

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    long long N, h[100005],i,ll,K,temp,mini,j;

    long long f1,f2;

    cin>>N>>K;

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

        cin>>h[i];

    long long M[100005]={0};

    M[N-2]=dif(h[N-1],h[N-2]);

    for(i=N-3;i>=0;i--)

    {

        mini=2000000000000;

        temp=K;

        for(ll=i+1;ll<N&&temp--;ll++)

        {



        f1=dif(h[ll],h[i])+M[ll];

        M[i]=min(mini,f1);

        mini=M[i];

        }

    }

    cout<<M[0]<<endl;

    return 0;

}




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

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

typedef long long LL;

const int maxn = 1000010;

const int inf = 0x3f3f3f3f;

LL n;

LL dp[maxn];

LL a[maxn];

LL k;

inline LL max(LL x, LL y) {

	return x > y ? x : y;

}

inline LL min(LL x, LL y) {

	return x < y ? x : y;

}

int main(){

	ios::sync_with_stdio(false);

	cin.tie(0);

	cout.tie(0);

	cin >> n >> k;

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

		cin >> a[i];

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

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

		dp[i] = inf;

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

		for (int j = i - 1; j >= max(1LL, i - k); j--)

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

	cout << dp[n];

	return 0;

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

//CLOCKS_PER_SEC

#define se second

#define fi first

#define ll long long

#define Pii pair<int,int>

#define Pli pair<ll,int>

#define ull unsigned long long

#define pb push_back

#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

const int N=1e5+10;

const int INF=0x3f3f3f3f;

const int mod=1e9+7;

using namespace std;

int n,val[N<<1];

int a[N],b[N];

int sum[N];

void add(int x){

	while(x<N*2){

		val[x]+=1;

		x+=x&-x;

	}

}

ll get(int x){

	ll ans=0;

	while(x>0){

		ans+=val[x];x-=x&-x;

	}

	return ans;

}

bool check(int x){

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

	ll tot=0;

	memset(val,0,sizeof(val));

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

		tot+=get(sum[i]+N);

		add(sum[i]+N);

	}

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

}

int main(){

	scanf("%d",&n);

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

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

	}

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

	int l=1,r=n;

	int ans=1;

	while(l<=r){

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

		if(check(b[mid])){

			ans=mid;

			l=mid+1;

		}

		else r=mid-1;

	}

	cout<<b[ans]<<endl;

	return 0;

}  

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

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<queue>

#define inl inline

#define re register

#define LL long long

#define MAXN 10100

using namespace std;

struct con

{

	int p;LL sum;

}hh[100100];

LL read()

{

    LL f=1,p=0;

    char c=getchar();

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

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

    return f*p;

}

void write(LL x)

{

    if(x<0)putchar('-'),x=-x;

    if(x/10)write(x/10);

    putchar(x%10+'0');

}

LL n,a[100100];

LL l=1000000000l,r,mid,ans,f[100100];

LL sum[100100];

inl LL lowbit(LL x){return x&(-x);}

inl bool cmp(const con&a,const con &b)

{

	if(a.sum==b.sum)return a.p<b.p;

	return a.sum<b.sum;

}

void add(int b){for(int i=b;i<=n;i+=lowbit(i))f[i]++;}

LL find(int a)

{

	LL u=0;

	for(int i=a;i>0;i-=lowbit(i))u+=f[i];

	return u;

}

bool check()

{

	ans=0;

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

	{

		if(a[i]<mid)hh[i].sum=-1;

		else hh[i].sum=1;

	}

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

		hh[i].sum+=hh[i-1].sum;

	for(int i=1;i<=n;i++)hh[i].p=i;

	sort(hh+1,hh+n+1,cmp);

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

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

	{

		add(hh[i].p);

		ans+=find(hh[i].p-1);

		if(hh[i].sum>=0)ans++; 

	}

	return 4*ans <n*(n+1);

}

int main()

{

	n=read();

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

	{

		a[i]=read();

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

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

	}

	while(l<r)

	{

		mid=(l+r+1)/2;

		if(check()) r=mid-1;

		else l=mid;

	}

	write(l);

	return 0;

}