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

using namespace std;

int arr[100005], memo[100005],k;



int dp(int n){

    if(n==0) return 0;

    if(memo[n]!=-1) return memo[n];

    int cost=1e9;

    for(int i=1; i<=k&&i<=n; ++i) cost=min(dp(n-i)+abs(arr[n]-arr[n-i]),cost);

    return memo[n]=cost;

}



int main(){

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

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

    ios_base::sync_with_stdio(0);

    cin.tie(0);

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

    int n;

    cin>>n>>k;

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

    cout<<dp(n-1)<<"\n";

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

    return 0;

}


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

using namespace std;



int arr[100100], dp[100100];



int main() {

  int n, k;

  cin >> n >> k;

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



  dp[0] = 0;

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



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

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

      if ( pos - step < 0 ) break;

      dp[pos] = min( dp[pos], dp[pos - step] + abs(arr[pos] - arr[pos - step]) );

    }

  }

  

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

  return 0;

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

#define INF 1e9

#define llINF 1e18

#define MOD 1000000007

#define pb push_back

#define mp make_pair 

#define F first

#define S second

#define ll long long

#define vi vector<ll>

#define vvi vector<vi>

#define substr(s,f,t) (s.substr(f-1,t-f+1))

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

#define Yes(hoge) cout<<((hoge)?"Yes":"No")<<endl;

#define YES(hoge) cout<<((hoge)?"YES":"NO")<<endl;

using namespace std;

struct Grid{ll x,y,t;};

struct Edge{ll to,cost;};

struct Graph{vector<vector<Edge>>E;int V;

  const ll Inf = llINF;const int MAX_V=201010;vector<ll>d;

  Graph(int n):E(n){d.resize(MAX_V);E.resize(n);V=n;}

  void init(){for(int i=0;i<MAX_V;i++)d[i]=Inf;}

  void add_edge(ll from,ll to,ll cost){E[from].pb({to,cost});}

};

int main(){

  cin.tie(0);

  ios::sync_with_stdio(false);

  ll n;cin>>n;

  priority_queue<ll>que;

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

    ll a;cin>>a;

    que.push(a);

  }

  ll ans=0;

  while(1){

    if((que.top())<n)break;

    ll num=que.top();

    que.pop();

    ll cnt=(num)/n;

    num-=((num)/n)*n;

    vi numm;numm.pb(num);

    ans+=cnt;

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

      numm.pb(cnt+que.top());

      que.pop();

    }

    for(int i=0;i<n;i++){que.push(numm[i]);}

  }

  cout<<ans<<endl;

  return 0;

}


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

#define INF 1e9

#define llINF 1e18

#define MOD 1000000007

#define pb push_back

#define mp make_pair 

#define F first

#define S second

#define ll long long

#define ull unsigned long long

#define vi vector<ll>

#define vvi vector<vi>

#define DBG_N(hoge) cerr<<"!"<<" "<<(hoge)<<endl;

#define DBG cerr<<"!"<<endl;

#define BITLE(n) (1LL<<((ll)n))

#define BITCNT(n) (__builtin_popcountll(n))

#define SUBS(s,f,t) ((s).substr((f)-1,(t)-(f)+1))

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

using namespace std;



int main(){

  cin.tie(0);

  ios::sync_with_stdio(false);

  ll n;cin>>n;

  priority_queue<ll>que;

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

    ll a;cin>>a;

    que.push(a);

  }

  ll ans=0;

  while(que.top()+ans>=n){

    ll num=que.top()+ans;

    que.pop();

    ll cnt=num/n;

    //cout<<cnt<<endl;

    que.push((num-(num/n)*n)-ans-cnt);

    ans+=cnt;

  }

  cout<<ans<<endl;

  return 0;

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

#include<ctype.h>

#include<string.h>

#include<algorithm>

#define il inline

#define rg register

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

using namespace std;

typedef long long ll;

const int O=100010;

il int gi(){

	rg int o=0,fl=1;char ch=getchar();

	while(!isdigit(ch)&&ch!='-')ch=getchar();

	if(ch=='-')fl=-1,ch=getchar();

	while(isdigit(ch))o=o*10+ch-'0',ch=getchar();

	return o*fl;

}

ll n,a[O],tree[O<<1],sum[O],l=0x3f3f3f3f,r,ans;

il void add(int x,ll v){

	for(;x<=2e5;x+=lowbit(x))tree[x]+=v;

}

il int query(int x){

	int tot=0;

	for(;x;x-=lowbit(x))tot+=tree[x];

	return tot;

}

il bool check(int x){

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

	ans=0;

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

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

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

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

		add(sum[i]+O,1ll);

	}

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

}

int main( ){

	n=gi();

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

		a[i]=gi();

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

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

	}

#define mid (l+r>>1)

	while(l<=r)

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

		else r=mid-1;

#undef mid

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

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 2.96785455792237x):
#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 <bits/stdc++.h>



using namespace std;

typedef long long ll;

typedef double dd;

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

#define endl "\n"

#define clr(n, r) memset(n,r,sizeof(n));



void fast() {



    cin.tie(0);

    cin.sync_with_stdio(0);

}

const int MAX = 1e5 + 9;

ll arr[MAX], dp[MAX];

int k,n;

int main() {

    fast();

    cin >> n>>k;

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

        cin >> arr[i];

    }

    clr(dp,10000);

    dp[0]=0;

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

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

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

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

        }

     //   cout<<dp[j]<<" ";

    }

    cout<<dp[n-1];

}

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

using namespace std;



#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)

template <typename Arg1>

void __f(const char* name, Arg1&& arg1) {

  cerr << name << " : " << arg1 << "\n";

}

template <typename Arg1, typename... Args>

void __f(const char* na, Arg1&& arg1, Args&&... args) {

  const char* c = strchr(na + 1, ',');

  cerr.write(na, c - na) << " : " << arg1 << " , ";

  __f(c + 1, args...);

}

#define endl "\n"

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

#define UNIQUE(v) sort(all(v)),v.erase(unique(all(v)),v.end())

typedef long long LL;

typedef pair <int,int> pii;

const double pi = acos(-1.0);

const double eps = 1e-8;

const int mod = 1e9 + 7;

const int inf = 1e9;

const LL INF = 1e18;

const int N = 1e5 + 5;



int main() {

  ios_base::sync_with_stdio(false);

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

  #ifdef LOCAL

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

  #endif // LOCAL

  int n, k;

  cin >> n >> k;

  vector <LL> h (n + 1);

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

  vector <LL> dp (n + 1, INF);

  dp[1] = 0;

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

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

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

    }

  }

  cout << dp[n] << endl;

  return 0;

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



using namespace std;



int main(){

   int k,x;

   cin>>k>>x;

   for (int i=-1000000;i<1000001;i++){

    if(i==x){

        for (i=x-(k-1);i<x+k;i++){

            cout<< i<<" ";

        }

    }

   }

   return 0;

}






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

#include <string>

#include <cmath>

using namespace std;

int main(){

int k,x;

cin>>k>>x;

int z=(x-k)+1;

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

    cout<<z<<" ";

    z+=1;

}

cout<<x<<" ";

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

    z+=1;

    cout<<z<<" ";



}

return 0;

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

using namespace std;

using LL = long long;

LL N, M, S, A[50];

inline LL ceil(LL d, LL n) {return (d+n-1)/n;}

inline bool ok(LL x) {

  if(M < S-x) return false;

  return accumulate(A,A+N,0ll,[&](LL s, LL a){return s+ceil(a+x+1-N, N+1);}) <= x;

}

int main() {

  scanf("%lld", &N);

  M=N*(N-1);

  for(auto i=0; i<N; ++i) scanf("%lld", A+i), S+=A[i];

  LL l = -1, h = 1e18;

  while(l+1 < h) {

    LL m = (l+h)>>1;

    if(ok(m)) h = m;

    else      l = m;

  }

  for(auto x=max(0ll,h-M); x<=h; ++x) if(ok(x)) {

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

    return 0;

  }

}

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

#include<algorithm>

using namespace std;

using LL = long long;

LL N, M, S;

LL A[50];

inline LL ceil(LL d, LL n) {return (d+n-1)/n;}

inline bool ok(LL x) {

  if(M < S-x) return false;

  LL s = 0;

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

    s += max(0ll, ceil(A[i]+x+1-N, N+1));

    if(x < s)return false;

  }

  return true;

}

int main() {

  scanf("%lld", &N);

  M=N*(N-1);

  for(auto i=0; i<N; ++i) scanf("%lld", A+i), S+=A[i];

  LL l = -1, h = 1e18;

  while(l+1 < h) {

    LL m = (l+h)>>1;

    (ok(m) ? h : l) = m;

  }

  for(auto x=max(0ll,h-M); x<=h; ++x) if(ok(x)) {

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

    break;

  }

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

using namespace std;

typedef long long ll;

typedef long long int lli;

typedef long double ld;

const int oo = 1e9;

const int mod = 1e9+9;

 

//Juan Pablo Betancourt Maldonado



const int nax = 1e5+103;

int n, k;

int dp[nax];

int a[nax];

int f(int i){

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

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

	int ans = abs(a[i]-a[i+1])+f(i+1);

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

		if(i+j<n) ans = min(ans, abs(a[i]-a[i+j])+f(i+j));

	}

	return dp[i]=ans;

}

int main(){

	cin>>n>>k;

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

	memset(dp, -1, sizeof dp);

	cout<<f(0)<<endl;

	return 0;

}

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

#define maxn (int)(2e5)

#define INF 1<<30

#define i64 long long

#define pii pair<i64,i64>

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

#define LB(x,v) lower_bound(all(x), v) - x.begin()

#define fread() freopen("in.txt", "r", stdin);

using namespace std;



int h[maxn+2], dp[maxn+2], n, k;



void init(int n){

    for(int i=0;i<=n;i++) dp[i] = INF;

}



int solve(int cur){

    if(cur >= n) return INF;

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



    if(dp[cur] != INF) return dp[cur];



    //int res = INF;

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

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

    }



    return dp[cur];

}

int main() {

    /*BEFORE SUBMIT, CHECK

    sample i/o format

    statements for debugging are removed/comment out

    global values / stl containers are initialized/cleared for each test (if needed)

    all array size are sufficient

    loop variable or output value doesn't cross min/max limit of input

    // */

    // #ifndef ONLINE_JUDGE

    //     fread();

    // #endif

    

    while(scanf("%d %d",&n, &k)==2){

        init(n);

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

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

        }

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

    }    

    return 0;

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



using namespace std;



int main()

{

    int n;

    cin >> n;

    

    int m;

    cin >> m;

    

    int l = 1;

	int r = n;

	

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

		int tl;

		cin >> tl;

		int tr;

		cin >> tr;

        

		if (l < tl) l = tl;

		if (tr < r) r = tr;

	}

	

	if (r < l) {

		cout << "0" << endl;

	} else {

		cout << r - l + 1;

	}



    return 0;

}

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



int main()

{

    int n;

    int m;

    

    scanf("%d", &n);

    scanf("%d", &m);

    

    int l = 1;

	int r = n;

	

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

		int tl;

		int tr;

		scanf("%d", &tl);

		scanf("%d", &tr);

        

		if (l < tl) l = tl;

		if (tr < r) r = tr;

	}

	

	if (r < l) {

		printf("0\n");

	} else {

		printf("%d", r - l + 1);

	}



    return 0;

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

using namespace std;



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

#define PER(i, a, b) for(int i = (a); i >= (b); i--)

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

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

#define SET(c, v) memset(c, v, sizeof c)

#define pi 3.14159265358979323846264338

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

#define INF 0x3f3f3f3f

#define mod 1000000007

#define pf push_front

#define pb push_back

#define mk make_pair

#define MAX 100000

#define S second

#define F first

typedef long long ll;

typedef long double lf;

typedef pair<int, int> ii;

typedef pair<int, ii> pii;

typedef unsigned long long int ull;

int v[MAX], pd[MAX], N, K;



int solve(int i) {

	int &ans = pd[i];

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

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

	if(ans != -1) return ans;

	ans = 1 << 30;

	REP(j, i+1, i+K) ans = min(ans, solve(j) + abs(v[i] - v[j]));

	return ans;

}



int main(int argc, char** argv) {

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

	rep(i, 0, N) scanf("%d", &v[i]);

	memset(pd, -1, sizeof pd);

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

	return 0;

}


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

using namespace std;

 

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

#define PER(i, a, b) for(int i = (a); i >= (b); i--)

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

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

#define pf push_front

#define pb push_back

#define mk make_pair

#define S second

#define F first

typedef long long ll;

typedef long double lf;

typedef pair<int, int> ii;

const int MAX = 1e5+5;

int N, K, a[MAX];

ll pd[MAX];



ll solve() {

	REP(i, 2, N) {

		pd[i] = (1LL << 60);

		rep(j, max(1, i-K), i)

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

	}

	return pd[N];

}



int main(int argc, char ** argv) {

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

	REP(i, 1, N) scanf("%d", &a[i]);

	printf("%I64d\n", solve());

	return 0;

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

using namespace std;

//long long a[200005];

int main()

{

    int N;

    cin >> N;

    string S;

    cin >> S;

    if (N >= S.length())

    {

        cout << S << endl;

    }

    else

    {

        cout << S.substr(0, N) << "..." << endl;

    }

}


// Faster C++ solution for the same problem (measured speedup: 5.252827434512703x):
#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<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll sum=0;

//vector<ll> sl;

ll dp[100000];

ll func(ll a[],ll n,ll size,ll k)

{

	ll s;

	if(dp[n]>=0)

	return dp[n];

	else

	{

     ll mini=INT_MAX;

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

     {

     	if(n>=i)

     	{

		 

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

     //cout<<"\nghj\n"<<s<<endl;

     if(s<mini)

     mini=s;

     }

     else 

     break;

	 }



	dp[n]=mini;

	if(n+1==size)

	return dp[n];

	else

	return func(a,n+1,size,k);

    }

}

main()

{

	ll n,a[100000],b[100000],k;

	cin>>n>>k;

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

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

	cin>>a[i];

	dp[0]=0;

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

	

	if(n>2)

	cout<<func(a,2,n,k)<<endl/*5 3

10 30 40 50 20*/;

	else

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

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

	cout<<dp[i]<<"  ";*/

}

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

using namespace std;

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

typedef long long ll;

#define lb lower_bound

#define ub upper_bound

#define pb push_back

#define mp make_pair

const ll inf=1e9+2;

int32_t main()

{

	IOS

	ll n,i,j,k;

	cin>>n>>k;

	vector<ll>v(n),dp(n,inf);

	for(auto &x:v)

		cin>>x;

	dp[0]=0;

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

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

	{

		for(j=i-k>0?i-k:0;j<i;j++)

		{

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

		}

    

	}

	cout<<dp[n-1];

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

using namespace std;

int n,h[100005],k,f[100005];

int main(){

	cin>>n>>k;

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

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

	f[1]=0;

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

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

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

	}

	cout<<f[n];

	return 0;

}

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



#define Solved int main()

#define pb push_back

#define mp make_pair

#define F first

#define S second

#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

#define forn(i, n) for(int i = 1; i <= n; i++)

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

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

#define pii pair<int, int>

#define ll long long

#define ull unsigned long long

#define ld long double

#define mii map<int, int>

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

using namespace std;



inline ll bip(ll x,ll n,ll mod){ll res=1;while(n){if(n&1){res=(res*x)%mod;}x=(x*x)%mod;n>>=1;}return res;}



const int maxn = 1e9;

const ll inf = 1e18;

const int mod = 998244353;

//const int mod = 1e9 + 7;

const int N = 1e5 + 10;



int n, k;

ll a[N];

ll dp[N];



void solve() {

    cin >> n >> k;



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

        cin >> a[i];



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

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

        dp[i] = inf;

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

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

        }

    }

    cout << dp[n];

}



Solved {

    SpeedForce;

	int tt = 1;

    //cin >> tt;

	while (tt--) {

		solve();

		cout << '\n';

	}



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

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

#include <stack>

#include <map>

#include <set>

#include <vector>

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

#define repd(i,x,n) for(int i=x;i<=n;i++)

#define pii pair<int,int>

#define pll pair<long long ,long long>

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

#define MS0(X) memset((X), 0, sizeof((X)))

#define MSC0(X) memset((X), '\0', sizeof((X)))

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define gg(x) getInt(&x)

using namespace std;

typedef long long ll;

inline void getInt(int* p);

const int maxn=1000010;

const int inf=0x3f3f3f3f;

/*** TEMPLATE CODE * * STARTS HERE ***/

ll n;

ll dp[maxn];

ll a[maxn];

ll k;

int main()

{

    gbtb;

    cin>>n>>k;

    repd(i,1,n)

    {

        cin>>a[i];

    }

    dp[1]=0;

    dp[0]=0;

    repd(i,2,n)

    {

        dp[i]=inf;

    }

    repd(i,2,n)

    {

        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;

}



inline void getInt(int* p) {

    char ch;

    do {

        ch = getchar();

    } while (ch == ' ' || ch == '\n');

    if (ch == '-') {

        *p = -(getchar() - '0');

        while ((ch = getchar()) >= '0' && ch <= '9') {

            *p = *p * 10 - ch + '0';

        }

    }

    else {

        *p = ch - '0';

        while ((ch = getchar()) >= '0' && ch <= '9') {

            *p = *p * 10 + ch - '0';

        }

    }

}

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

#include <cstring>

#include <algorithm>

#define ll long long

#define inf 1<<30

#define il inline 

#define in1(a) read(a)

#define in2(a,b) in1(a),in1(b)

#define in3(a,b,c) in2(a,b),in1(c)

#define in4(a,b,c,d) in2(a,b),in2(c,d)

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;

/*===================Header Template=====================*/

#define N 100001

#define lowbit(x) x&-x

int c[N*10];

int n,a[N],s[N*10],f[N];

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){

	//x=8;

    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(){

    in1(n);

    int l=0,r=0;

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

        in1(a[i]);f[i]=a[i];

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

    }r=n;sort(f+1,f+n+1);

    int ans=0;l=1;

    while(l<=r){

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

        if(check(f[mid]))l=mid+1;

        else r=mid-1;

    }

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

}

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

#include<algorithm>

#include<cmath>

using namespace std;

#define INF 1000000000;

int a[100005],sum[100005],save[100005];

typedef long long ll;

ll to,to1;

int n;int maxl,minl;

void sortl(int left,int right)

{

    if(left==right)

        return ;

    int mid=(right+left)/2;

    sortl(left,mid);

    sortl(mid+1,right);

    int l=left,l2=mid+1,r=left;

    while(l<=mid&&l2<=right)

    {

        if(sum[l]<sum[l2])

            save[r++]=sum[l++];

        else

        {

            to1+=l-left;

            save[r++]=sum[l2++];

        }

    }

    while(l<=mid)

        save[r++]=sum[l++];

    while(l2<=right)

    {

        to1+=l-left;

        save[r++]=sum[l2++];

    }

    for(int i=left;i<=right;i++)

        sum[i]=save[i];

}

bool ck(int x)

{

    to1=0;

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

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

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

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

    sortl(0,n);

    return to1>=to/2+1;

}

int main()

{

    maxl=-INF;minl=INF

    scanf("%d",&n);

    to=0;

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

    {

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

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

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

        to+=i;

    }

    while(minl<maxl)

    {

        int mid=(minl+maxl)/2;

        if(ck(mid))

            maxl=mid;

        else

            minl=mid+1;

    }

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

}