stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:




#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pii pair<int, int>

#define ff first

#define ss second



int main() {

    ll n, ai, bi, ci, sum = 0, q;

    int arra[100002];

    memset(arra, 0, sizeof(arra));

    cin >> n;

    while(n--){

        cin >> ai;

        arra[ai]++;

        sum += ai;

    }

    cin >> q;

    while(q--){

        cin >> bi >> ci;

        sum = sum - (bi*arra[bi]) + (ci*arra[bi]);

        arra[ci] += arra[bi];

        arra[bi] = 0;

        cout << sum << '\n';

    }

    return 0;

}

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

#define rush() int T;scanf("%d",&T);int kase=1;while(T--)

#define pb(x) push_back(x)

#define pr pair<int,int>

#define mem(a) memset(a,0,sizeof(a))

#define  fi first

#define  se second

using namespace std;

typedef long long ll;

const ll maxn=2e6+5;

const ll mod=1e9+7;

ll quickpow(ll x,ll y,ll mod){ll ans=1;while(y){if(y&1)ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;}



int a[maxn]={0};



int main()

{

    int n;

    cin>>n;

    ll sum=0;

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

    {

        int x;

        cin>>x;

        sum+=x;

        a[x]++;

    }

    int q;

    cin>>q;

    while(q--)

    {

        int b,c;

        cin>>b>>c;

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

        a[c]+=a[b];

        a[b]=0;

        cout<<sum<<endl;

    }

    return 0;

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



using namespace std;



#define ff first

#define ss second

#define int long long

#define pii pair<int,int>

#define mp make_pair



int memo[100000],v[100000],k;



int calcpulo(int id){

	if(memo[id]==INT_MAX){

		int menor,i,calc,aux;

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

			calc=id-k+i;

			if(calc>=0){

				menor=calcpulo(calc);

				aux=abs(v[id]-v[calc])+menor;

				if(memo[id]>aux)memo[id]=aux;

			}		

		}

	}

	return memo[id];	

}



signed main(){

	ios_base::sync_with_stdio(false);

	cin.tie(0);

	cout.tie(0);

	int n,i;

	cin>>n>>k;

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

	memo[0]=0;

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

		memo[i]=INT_MAX;

	}

	cout<<calcpulo(n-1)<<endl;	

}

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

#define inf 2000000000

int n,k;

int h[100002]={100000},f[100002]={};

int min(int a,int b)

{

	return a<b? a:b;

}

int max(int a,int b)

{

	return a>b? a:b;

}

int abs(int x)

{

	return x<0? -x:x;

}

int main()

{

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

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

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

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

	{

		f[i]=inf;

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

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

	}

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

	return 0;

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

#include <vector>

#include <algorithm>

#include <numeric>

#include <cmath>

#include <set>

#include <tuple>

#include <functional>

#include <map>

#include <unordered_map>

#include <queue>

#include <tuple>



using namespace std;



#define endl '\n'



using ull = unsigned long int;

using ll = long long;



int main() {

  ios_base::sync_with_stdio(false);

  cin.tie(nullptr);

  const int precision = 13;

  cout.precision(precision);

  cout.setf(ios_base::fixed);



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

  vector<ll> s(k+1), dp(k+1, 1e9 + 10);

  ++k;

  dp[1] = 0;

  cin >> s[1];

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

    cin >> s[i%k];

    dp[i%k] = dp[(i-1)%k] + abs(s[i%k] - s[(i-1)%k]);

    for (int l = 2; l < k and l < i; ++l) {

      dp[i%k] = min(dp[(i-l)%k] + abs(s[(i-l)%k] - s[i%k]), dp[i%k]);

    }

  }



  cout << dp[n%k] << endl;



  return 0;

}


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

#include<cmath>

#include<algorithm>

using namespace std;

const int maxn=1e5 + 5;

int main()

{

	int dp[maxn];

	int h[maxn];

	int n,k;

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

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

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

		dp[1] = 0;

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

	    	dp[i]=1e9;

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

				if(i==j) break;

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

				}

	}

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

	}

	return 0;

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

#include<iostream>

#include<algorithm>

#include<queue>

#define inf 0x3f3f3f3f

using namespace std;

typedef long long LL;

const int maxn = 1e5+5;



int a[maxn],dp[maxn];



int main(){

	int n,k;

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

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

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

		for(int j = k; j >= 1; j--){

			if(i - j > 0){

				if(i > k){

					if(j == k) dp[i] = dp[i-j] + abs(a[i] - a[i-j]);

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

				}

				else{

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

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

				}

			}

		}

	}

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

}

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

#include<cmath>

#include<algorithm>

using namespace std;

const int maxn=1e5 + 5;

int main()

{

	int dp[maxn];

	int h[maxn];

	int n,k;

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

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

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

		dp[1] = 0;

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

	    	dp[i]=1e9;

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

				if(i==j) break;

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

				}

	}

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

	}

	return 0;

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

#include<cstring>

#include<algorithm>

using namespace std;

typedef int int_;

#define int long long

#define maxn 200010

const int inf=1e9+7;

inline int read(){

	int ret=0,ff=1;

	char ch=getchar();

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

		if(ch=='-') ff=-ff;

		ch=getchar();

	}

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

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

		ch=getchar();

	}

	return ret*ff;

}



int gcd(int a,int b){

	return b?gcd(b,a%b):a;

}

int ksm(int a,int b,int p){

	int ret=1;

	while(b){

		if(b&1) ret=ret*a%p;

		a=a*a%p;

		b>>=1;

	}

	return ret%p;

}

int a[maxn],num[maxn];

int_ main(){

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

	int n=read();

	int ans=0;

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

		a[i]=read();

		ans+=a[i];

		++num[a[i]];

	}

	

	int q=read();

	while(q--){

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

		int x=read(),y=read();

		ans+=(y-x)*num[x];

		num[y]+=num[x];

		num[x]=0;

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

	}

	return 0;

} 

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

using namespace std;

typedef long long ll;

map<ll,ll>mp;



int main(){

    ll n;scanf("%lld",&n);

    ll sum=0;

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

        ll num;

        scanf("%lld",&num);

        mp[num]++;

        sum+=num;

    }

    ll q;scanf("%lld",&q);

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

        ll b,c;scanf("%lld%lld",&b,&c);

        mp[c]+=mp[b];

        sum+=mp[b]*(c-b);

        mp[b]=0;

        cout<<sum<<endl;

    }

    return 0;

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

#include<cstring>

#include<algorithm>

#include<cstdio>

using namespace std;

#define MAXN 100000 + 10

#define ll long long int

ll N[MAXN];

ll dp[MAXN];

#define INF 0x3f3f3f3f;

int main()

{

    ll n,k;

    cin>>n>>k;

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

        cin>>N[i],dp[i] = INF;

    dp[0] = 0;

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

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

            if(j >= 0)

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

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

    return 0;

}

//

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

#include<cmath>

#include<algorithm>

using namespace std;

const int maxn=1e5 + 5;

int main()

{

	int dp[maxn];

	int h[maxn];

	int n,k;

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

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

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

		dp[1] = 0;

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

	    	dp[i]=1e9;

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

				if(i==j) break;

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

				}

	}

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

	}

	return 0;

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

using namespace std;

#define mod 1000000007



int main()

{

    int n;



    scanf("%d", &n);

    long long s = 1;

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

        s = s * i % mod;

    }

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

}


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

#include <algorithm>

using namespace std;



int main()

{

	int n,i;

	long long sum=1;

	scanf("%d",&n);

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

	{

		sum*=i;

		sum%=(1000000000+7);

	}

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

	return 0;

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

#include<cstring>

#include<algorithm>

#define ll long long

#define int long long

#define MN 100005

using namespace std;

inline int in(){

    int x=0;bool f=0;char c;

    for (;(c=getchar())<'0'||c>'9';f=c=='-');

    for (x=c-'0';(c=getchar())>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0');

    return f?-x:x;

}

int c[MN<<2],d[MN],sum[MN],a[MN],b[MN];

int n,tot,l,r,res;

ll num;

inline void add(int x,int v){

	for (int i=x;i<=((n<<1)|1);i+=i&(-i)) c[i]+=v; 

}

inline int query(int x){

	int res=0;

	for (int i=x;i;i-=i&(-i)) res+=c[i];

	return res;

}

inline bool check(int x){

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

	for (int i=1;i<=n;++i) d[i]=(sum[i]<<1)-i+n+1;d[0]=n+1;

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

	add(d[0],1);num=0ll;

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

	num+=1ll*(query(((n<<1)|1))-query(d[i])),add(d[i],1);

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

}

signed main()

{

	n=in();

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

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

	tot=unique(b+1,b+n+1)-b-1;

	l=0,r=tot,res=0;

	while (l<=r){

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

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

		else l=mid+1;

	}

	printf("%d",b[res]);return 0;

}

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

    in1(n);

    int l=0,r=0;

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

        in1(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>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<stack>

#include<queue>

#include<vector>

#include<set>

#include<string>

#include<cmath>

#include<map>

#include<bitset>

#include<utility>

//#include<unordered_map>

#ifdef LOCAL

#include"file.h"

#endif



using namespace std;



typedef long long LL;

typedef unsigned long long ULL;

const double eps = 1e-12;

const double Pi = 3.1415926535897932;

const int dir[4][2] = { -1,0,1,0,0,-1,0,1 };

//const int dir[8][2] = { -2,-1,-2,1,2,-1,2,1,-1,2,-1,-2,1,2,1,-2 };

















const int maxn = 2e5 + 5;









int f[maxn];

int h[maxn];



int n, k;



int main() {

#ifdef LOCAL

	fileopen();

#endif



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

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

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



		memset(f, 63, sizeof(f));

		f[1] = 0;



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

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

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

			}

		}

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

	}





#ifdef LOCAL

	fileclose();

#endif

	return 0;

}


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

#include<cstring>

#include<algorithm>

#include<cstdio>

using namespace std;

#define MAXN 100000 + 10

#define ll long long int

ll N[MAXN];

ll dp[MAXN];

#define INF 0x3f3f3f3f;

int main()

{

    ll n,k;

    cin>>n>>k;

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

        cin>>N[i],dp[i] = INF;

    dp[0] = 0;

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

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

            if(j >= 0)

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

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

    return 0;

}

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

#include<cstdio>

#include<math.h>

#include<algorithm>

#include<map>

#include<set>

#include<bitset>

#include<stack>

#include<queue>

#include<string>

#include<cstring>





using namespace std;

typedef long long LL;

const int maxn=2e6+7;

LL n;

LL tot=0;

LL mn=0x3f,mx=-0x3f;

LL a[maxn];

LL bit[maxn];



struct node {

LL val,pos;

}arr[maxn];



bool cmp(node n1,node n2)

{

    return n1.val==n2.val?n1.pos<n2.pos:n1.val<n2.val;

}



void update(LL x,LL val)

{

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

    {

        bit[x]+=val;

    }

}



LL getsum(LL x)

{

    LL ans=0;

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

    {

        ans += bit[x];

    }

    return ans;

}







bool check(LL x){

    memset(bit,0,sizeof(bit));

     memset(arr,0,sizeof(arr));





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

    {

        if(a[i]<=x)arr[i].val=-1;

        else arr[i].val=1;

        arr[i].pos=i+1;

    }



    arr[0].val=0;

	arr[0].pos=1;



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

	arr[i].val+=arr[i-1].val;

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



	LL ans=0;

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

    {

        ans+=(i-getsum(arr[i].pos));

        update(arr[i].pos,1);

    }

	return ans*2 > tot;

}





int main(){

   scanf("%lld",&n);



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

    {

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

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

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

   	 tot+=i;

   }



   LL l=mn,r=mx;

   while(r-l>1)

    {

   	  LL mid=(l+r)/2;

   	 if(check(mid)) r=mid;

   	 else l=mid;

   	 //printf("s%d",mid);

   }

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



   return 0;

}


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

#include<algorithm>

using namespace std;

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

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

int n,a[110000],l,r,mi,f[220000];

long long m;

inline void add(int x){

	while (x<=n+n){

		f[x]++;

		x+=x&(-x);

	}

}

inline long long ask(int x){

	long long ans=0;

	while (x){

		ans+=f[x];

		x-=x&(-x);

	}

	return ans;

}

inline bool che(int x){

	int s=n+1;long long ans=0;//s=n TLE

	fo(i,0,n+n) f[i]=0;

	add(s);

	fo(i,1,n){

		if (a[i]>=x) s++;else s--;

		ans+=ask(s);

		add(s);

	}

	return ans>=m;

}

int main(){

	scanf("%d",&n);

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

	m=n*1ll*(n+1)/2;

	m=(m+1)/2;

	l=0x7fffffff;r=0;

	fo(i,1,n){

		if (a[i]<l) l=a[i];

		if (a[i]>r) r=a[i];

	}

	l--;r++;

	while (l+3<r){

		mi=(l+r)>>1;

		if (che(mi)) l=mi+1;else r=mi-1;

	}

	fd(i,r+1,l-1) if (che(i)){//che(mi)!!!

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

		return 0;

	}

	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; ++ i)  // 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.7926679395545575x):
#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;

#define ll long long

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

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

#define show(x) {for( auto ii : x) cout << ii << en; cout << endl;}

#define shop(n,x) {for(int i = 0; i < n; i++) cout << x << en; cout << endl;}

#define ff first

#define ss second

#define sq(x) (x*x)

#define endl '\n'

#define en " "

#define pb push_back

#define mpair make_pair

ll mod=1000000007;

double pi=3.1415926536;

ll n, k;

ll dp[200003];

ll cost(ll a[], ll idx)

{

	if(dp[idx] != -1)

		return dp[idx];



	if(idx >= n-2)

		return abs(a[n-1] - a[idx]);

	

	ll m = mod, p = mod;

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

	{

		if(idx + i >= n)

			break; 

		p = abs(a[idx + i] - a[idx]) + cost(a, idx + i);

		m = min(m, p);

	}

	return dp[idx] = m;

}

int main()

{

	fastio();

	int tt = 1;

	//cin >> tt;

	while(tt--)

	{

		// go fast 		check		//		CHECK -> if()   else if()

		

		ll x = 0, m = 0, y = 0, d = 1;

		cin >> n >> k;

		ll a[n];

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

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

			cin >> a[i];



		cout << cost(a, 0) << endl;

	}

}

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

using namespace std;

#define ll long long

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

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

#define show(x) {for( auto ii : x) cout << ii << en; cout << endl;}

#define shop(n,x) {for(int i = 0; i < n; i++) cout << x << en; cout << endl;}

#define ff first

#define ss second

#define sq(x) (x*x)

#define endl '\n'

#define en " "

#define pb push_back

#define mpair make_pair

ll mod=1000000007;

double pi=3.1415926536;

ll n;

// ll dp[200003];

int main()

{

	fastio();

	int tt = 1;

	//cin >> tt;

	while(tt--)

	{

		// go fast 		check		//		CHECK -> if()   else if()

		

		ll x=0, m=0, y=0, d=1, k=mod;

		cin >> n >> k;

		ll a[n], dp[n];

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

			cin >> a[i];



		dp[n - 1] = 0;

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



		for(int i = n-3; i >= 0; i--)

		{

			dp[i] = mod;

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

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

		}

				

		cout << dp[0] << endl;

	}

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

using namespace std;

typedef long long ll;

const int inf=0x3f3f3f3f;

int n,k;

int h[100000+10];

int dp[100000+10];

int cha(int x,int y)

{

    if(x>=y)    return x-y;

    else    return y-x;

    return  y-x;

}

int main()

{

    cin>>n>>k;

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

    dp[0]=0;

    dp[1]=cha(h[1],h[0]);

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

    {

        int least=inf;

        for(int j=max(0,i-k);j<i;j++)

        {

            least=min(least,dp[j]+cha(h[i],h[j]));

        }

        dp[i]=least;

    }

    cout<<dp[n-1];

    return 0;

}

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

#include <algorithm>

#include <cmath>

using namespace std;



int h[(int)1e5], dp[(int)1e5], K, N;





int main()

{

	K = N = 0;

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

	{

		dp[j] = 1e9;

	}

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

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

	{

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

	}

	dp[1] = 0;

	dp[2] = dp[1] + abs(h[1] - h[2]);

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

	{

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

		{

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

		}

	}

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

	return 0;	

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

#include<cstdlib>

#include<cmath>

#include<iostream>

#include<algorithm>



using namespace std;



const int Max = 1e9 + 7;

typedef long long ll;

ll ans;



int main(){

	int i, j, n, m;

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

		ans = 1;

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

			ans *= i;

			ans %= Max;

		}

		cout << ans << endl;

	}

	return 0;

}

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

const long long MOD=1e9+7;

int n;

long long ans=1;

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n;i++) ans=(ans*i)%MOD;

	printf("%lld",ans);

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

using namespace std;

#define fi first

#define se second

typedef long long ll;

const ll mod=1000000007;

ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}

ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}



int dp[100001];

vector<int> stone;

int k;

int solve(int n){

	if(dp[n] > -1) return dp[n];

	if(n == 0){

		return dp[n] = 0;

	}

	int minimum = INT_MAX;

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

		if(n - i >= 0){

			minimum = min(minimum, solve(n-i) + abs(stone[n] - stone[n - i]));

		}

	}

	return dp[n] = minimum;

}

int main()

{

	ios::sync_with_stdio(false);

  	cin.tie(0);

  	int n;

  	cin >> n >> k;

  	stone.resize(n);

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

  		int m;

  		cin >> m;

  		stone[i] = m;

  	}

  	for(int i = 0; i < 100001; i++) dp[i] = -1;

  	reverse(stone.begin(), stone.end());

  	cout << solve(n-1) << endl;

	return 0;

}


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

using namespace std;



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

#define trav(a, x) for(auto& a : x)

#define pb push_back

#define mp make_pair

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

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

#define endl '\n'



typedef long long ll;

typedef pair<int,int> pii;

typedef pair<ll,ll> pll;

typedef vector<int> vi;

typedef vector<ll> vll;



const ll mod=1000000007;

//head



int main()

{

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



    int n, k;

    cin >> n >> k;

    vi a(n);

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

    vi dp(n,1 << 30);

    dp[0] = 0;



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

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

            if(i+j < n)

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

        }

    }

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

    return 0;

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

using namespace std;



signed main()

{

	int k;cin>>k;

	string a;cin>>a;

	if(a.length()<=k)cout<<a<<endl;

	else{

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

		cout<<a[i];

		cout<<"..."<<endl;

	}

	return 0;

}

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

	}

}