stablegradients/pie-gem5-pairs huggingface dataset:
// 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.9581600503111092x):
//Copyright(c)2018 Mstdream

#include<bits/stdc++.h>

#define LL long long

using namespace std;

const int N=200010;

int t[N],a[N],b[N],n;

void add(int x){

	for(;x<=2*n+1;x+=x&-x)t[x]++;

}

int qry(int x){

	int ret=0;

	for(;x;x-=x&-x)ret+=t[x];

	return ret;

}

bool check(int x){

	x++;

	LL ret=0;

	for(int i=1;i<=2*n;i++)t[i]=0;

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

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

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

		add(b[i-1]+n+1);

		ret+=qry(b[i]+n+1);

	}

	ret=(LL)n*(n+1)/2-ret;

	return ret>=((LL)n*(n+1)/2+2)/2;

}

int main(){

	scanf("%d",&n);

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

	int l=1,r=1e9+1;

	while(l!=r){

		int mid=l+r>>1;

		if(check(mid))r=mid;

		else l=mid+1;

	}

	cout<<l<<endl;

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

using namespace std;

#define N (int)2e5

int n,k,memo[N],c[N];



int dp(int curr) {

    if (curr == n) return 0;

    if (curr > n) return 1e9;

    int &sol = memo[curr];

    if (sol != -1) return sol;

    int keep = INT_MAX;

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

        keep = min(

            dp(curr + i) + abs(c[curr] - c[curr + i]) ,

            keep

        );

    }

    return sol = keep;

}



int main() {

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

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

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

    memset (memo , -1 , sizeof memo);

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

}

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

#include <algorithm>



using namespace std;



int main(){

    int N, K;

    cin >> N >> K;



    int p1, px, mins[N], alturas[N];



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

        if(i < N){

            cin >> px;

            alturas[i] = px;

        }

        else {

            cout << mins[N-1];

        }

        if(i == 0){

            p1 = px; 

        }

        else if(i == 1){

            mins[1] = abs(p1 - px);

        }

        else {

            int saltos = min(K, min(N, i));

            mins[i] = 1000000000; 

            for(int j = 0; j < saltos; j++){

                if(j == i-1){

                    mins[i] = min(mins[i], abs(p1 - px));

                }

                else {

                    int ult_salto = abs(px - alturas[i-j-1]);

                    mins[i] = min(mins[i], ult_salto + mins[i-j-1]); 

                }

            }

        }

    }

    return 0;

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



using namespace std;



int n,s;

int mem[100][100][100];

int f(int deps,int cnt,int sum)

{

    if(mem[deps][cnt][sum])return mem[deps][cnt][sum];

    if(cnt == n && sum == s)return 1;

    if(deps == 10) return 0;

    return mem[deps][cnt][sum]=f(deps + 1,cnt + 1,sum + deps)+f(deps + 1,cnt,sum);

}



int main()

{

    while(1){

    memset(mem,0,sizeof(mem));

    cin >> n >> s;

    if(n == 0 && s == 0)break;

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

    }

    return 0;

}

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



using namespace std;



int n,s;



int F(int deps,int cnt,int sum){

    if(deps == 10){

        if(cnt == n && sum == s)return 1;

        return 0;

    }

    return F(deps + 1,cnt + 1,sum + deps) + F(deps + 1,cnt,sum);

}



int main()

{

    while(1){

        cin >> n >> s;

        if(n == 0 && s == 0)break;

        cout << F(0,0,0) << endl;

    }



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

#include <ext/pb_ds/assoc_container.hpp>

#define F first

#define S second

#define PB push_back

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

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

using namespace __gnu_pbds;

using namespace std;



typedef long long ll;

typedef vector<int> vi;

typedef pair<int,int> pi;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;



const int OO = 1e9+7;

const int MOD = 1e9+7;

const int N = 1e5+7;



int mem[N];

int n,k;

int h[N];

int dp(int i)

{

    int &ret = mem[i];

    if (ret != -1) return ret;

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

    ret = OO;

    REP(j,1,k)

    {

        if (i+j >= n) break;

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

    }

    cerr << i << ' ' << ret << endl;

    return ret;

}



int main()

{

    //ios::sync_with_stdio(0);

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

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

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

    memset(mem,-1,sizeof mem);

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

    REP(i,0,n-1) scanf("%d",&h[i]);

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



    return 0;

}


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

#include <ext/pb_ds/assoc_container.hpp>

#define F first

#define S second

#define PB push_back

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

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

using namespace __gnu_pbds;

using namespace std;



typedef long long ll;

typedef vector<int> vi;

typedef pair<int,int> pi;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;



const ll OO = 1e18+7;

const int MOD = 1e9+7;

const int N = 1e5+7;



ll dp[N];

int n,k;

ll h[N];



int main()

{

    //ios::sync_with_stdio(0);

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

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

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



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

    REP(i,0,n-1) scanf("%lld",&h[i]);



    REP(i,1,n-1)

    {

        dp[i] = OO;

        REPI(j,i-1,i-k)

        {

            if (j < 0) break;

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

        }

    }

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

    return 0;

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



using namespace std;



int dp[100000],v[100000];



int calcdp(int k,int id){

	if(dp[id]==INT_MAX){

		int aux;

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

			if(id-k+i>=0){

				aux=calcdp(k,id-k+i);

				if(abs(v[id]-v[id-k+i])+aux<dp[id]){

					dp[id]=abs(v[id]-v[id-k+i])+aux;

				}

			}

		}

	}

	return dp[id];

}



int main(){

	int n,k;

	cin>>n>>k;

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

		cin>>v[i];

		dp[i]=INT_MAX;

	}

	dp[0]=0;

	dp[n-1]=calcdp(k,n-1);

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

}

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

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

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

int main()

{

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

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

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

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

	f[1]=0;

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

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

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

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

	return 0;

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

#include <vector>

#include <map>

#include <list>

#include <set>

#include <stack>

#include <queue>

#include <string>

#include <utility>

#include <algorithm>

#define REP(i,n) for(int i = 0; i < n; i++)

#define REP(j,n) for(int j = 0; j < n; j++)



using namespace std;

typedef pair<int, int> P;



int main() {

    int n,r,l;

    cin >> n;

    cin >> r;

    cin >> l;

    int list[n+1];

    int time[n+1];

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

        list[i] = 0;

        time[i] = 0;

    }

    int top = 0;

    int id  = 1;

    int nowtime = 0;

    int timemax = 0;

    int timemaxid = 0;

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

        int d,t,x;

        cin >> d;

        cin >> t;

        cin >> x;

        time[id] += t - nowtime;

        if(time[id] > timemax) {

            timemax = time[id];

            timemaxid = id;

        }

        nowtime = t;

        list[d] += x;

        if(id == d) {

            top += x;

        }

        if(x < 0 && d == id) {

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

                if(top < list[j] || (top == list[j] && j < id)) {

                    top = list[j];

                    id = j;

                }

            }

            

        }

        if(x > 0 && d != id) {

            if(top < list[d] || (top == list[d] && d < id)) {

                top = list[d];

                id = d;

            }

        }



    }

    time[id] += l - nowtime;

    if(time[id] > timemax) {

        timemax = time[id];

        timemaxid = id;

    }

    cout << timemaxid << "\n";

}

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


#include <cstdio>





using namespace std;

int lis[100000];

int tim[100000];

int main() {

    int n,r,l;

    scanf("%d %d %d",&n,&r,&l);



    int top = 0;

    int id  = 1;

    int nowtime = 0;

    int timemax = 0;

    int timemaxid = 0;

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

       

        int d,t,x;

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

        tim[id] += t - nowtime;

        if(tim[id] > timemax) {

            timemax = tim[id];

            timemaxid = id;

        }

        nowtime = t;

        lis[d] += x;

        if(id == d) {

            top += x;

        }

        if(x < 0 && d == id) {

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

                if(top < lis[j] || (top == lis[j] && j < id)) {

                    top = lis[j];

                    id = j;

                }

            }

            

        }

        if(x > 0 && d != id) {

            if(top < lis[d] || (top == lis[d] && d < id)) {

                top = lis[d];

                id = d;

            }

        }



    }

    tim[id] += l - nowtime;

    if(tim[id] > timemax) {

        timemax = tim[id];

        timemaxid = id;

    }

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

}
// 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 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);

}

// Faster C++ solution for the same problem (measured speedup: 0.7566987251015704x):
// ===================================

//   author: M_sea

//   website: http://m-sea-blog.com/

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

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <cmath>

#define re register

using namespace std;

typedef long long ll;



inline int read() {

    int X=0,w=1; char c=getchar();

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

    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();

    return X*w;

}



const int N=100000+10;



int n,mx;

int a[N],s[N],S[N];



int c[N<<1];

inline int lowbit(int x) { return x&-x; }

inline void add(int x,int y) {

    for (;x<=mx;x+=lowbit(x)) c[x]+=y;

}

inline int query(int x) {

    int res=0;

    for (;x;x-=lowbit(x)) res+=c[x];

    return res;

}



inline int check(int mid) {

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

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

        if (a[i]<mid) s[i]=-1;

        else s[i]=1;

    }

    ll res=0;

    for (re int i=1;i<=n;++i) s[i]+=s[i-1],res+=(s[i]>=0);

    for (re int i=1;i<=n;++i) s[i]+=n+1,mx=max(mx,s[i]);

    for (re int i=1;i<=n;++i) res+=query(s[i]),add(s[i],1);

    ll cnt=1ll*n*(n-1)/2+n;

    return cnt-res<cnt/2+1;

}



int main() {

    n=read();

    for (re int i=1;i<=n;++i) S[i]=a[i]=read();

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

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

    int L=1,R=m,ans=0;

    while (L<R) {

        int mid=(L+R+1)>>1;

        if (check(mid)) L=mid;

        else R=mid-1;

    }

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

    return 0;

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

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

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

#define fore(i,a) for(auto &i:a)

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

//#pragma GCC optimize ("-O3")

using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }

typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }

//------------------------------------------------------------------------------

//------------------------------------------------------------------------------

int N, K;

vector<int> h;



int dp[101010];



int Solve(int pos)

{

    if (dp[pos] >= 0) return dp[pos];



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

    if (pos >= N) return inf;



    int res = inf;

    rep(i, 1, K + 1)

    {

        if (pos + i <= N - 1)

        {

            chmin(res, abs(h[pos] - h[pos + i]) + Solve(pos + i));

        }

    }

    return dp[pos] = res;

}



void _main()

{

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

    cin >> N >> K;

    h.resize(N);

    rep(i, 0, N) cin >> h[i];

    cout << Solve(0) << endl;

}


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

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

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

#define fore(i,a) for(auto &i:a)

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

//#pragma GCC optimize ("-O3")

using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }

typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }

//------------------------------------------------------------------------------

//------------------------------------------------------------------------------

void _main()

{

    int N, K;

    cin >> N >> K;

    vector<int> h(N);

    rep(i, 0, N) cin >> h[i];



    vector<int> dp(N + 1, inf);

    dp[0] = 0;

    rep(i, 0, N)

    {

        rep(j, 1, K + 1)

        {

            if (i + j >= N) continue;

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

        }

    }

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

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

using namespace std;

 

 

int main() {

int n, k; 

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

	vector<int> arr(n), dp(n, INT_MAX);

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

	

	dp[0]=0;

	

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

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

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

			

		}

	}

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



	return 0;

}


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

#include<cstdio>

#include<map>

#include<algorithm>

using namespace std;

const int MAXN = 100010;

long long sum[MAXN];

int a[MAXN],aa[MAXN],b[MAXN],c[MAXN];

int n;

int lowbit(int x){return x&(-x);}

void update(int x,int n){

	for (int i=x;i<=n;i+=lowbit(i)) {

		sum[i]++;

	}

}

int getSum(int x) {

	int ans = 0;

	for (int i=x;i>0;i-=lowbit(i)) {

		ans += sum[i];

	}

	return ans;

}

long long check(int x) {

	b[0] = 0;c[0] = 0;

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

		if (a[i]<=x) b[i] = 1;

		else b[i] = -1;

	}

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

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

		c[i] = b[i];

	}

	sort(c,c+1+n);

	int cnt = 1;

	map<int,int> mp;

	mp[c[0]] = 1;

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

		if (c[i]!=c[i-1]) {

			cnt++;

			mp[c[i]] = cnt;

		}

	}

	for (int i=0;i<=cnt;i++) sum[i]=0;

	long long res = 0;

	update(mp[0],cnt);

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

		res += getSum(mp[b[i]]-1);

		update(mp[b[i]],cnt);

	}

	return res;

}

int main()

{

	scanf("%d",&n);

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

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

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

	long long k = 1LL * n*(n+1)/2/2+1;

	int l = 1,r = n,mid,ans;

	while(l<=r) {

		mid = (l+r) / 2;

		if (check(aa[mid])>=k) {

			ans = aa[mid];

			r = mid - 1;

		}

		else l = mid + 1;

	}

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

}

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

 

#define ll long long

#define X first

#define Y second

#define MP make_pair

#define ld long double

 

using namespace std;

 

const int N = 5e5 + 123;

const ll mod = 1e9 + 7;



ll a[N], dp[N];

int n, k;



int main (){

	ios::sync_with_stdio(0);

	cin.tie(0);

	cout.tie(0);



	cin >> n >> k;

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

		cin >> a[i];

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

		dp[i] = N * 1ll * N;

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

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

		}

	}

	cout << dp[n];

}

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



using namespace std;



#define ll long long

#define PI acos(-1.0)



ll dp[100105];

int n, k,arr[100005];



ll func(int indx)

{

	if(indx == n) return 0;

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

	int len = min(indx+k, n);

	ll total = INT_MAX;

	for(int i = indx+1; i <= len;i++)

	{

		ll ans = abs(arr[indx]-arr[i]) + func(i);

		total = min(total,ans);

	}

	return dp[indx] = total;

}



int main()

{   

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

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

    {

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

	}

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

	ll ans = func(1);

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

	    	

	return 0;

}


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

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;

}

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

#include <cstring>

#include <algorithm>

using namespace std; 

typedef long long LL;

const int MAXN=1E5+10;

int f[MAXN],sum[MAXN],tong[MAXN],a[MAXN];

long long sumans;



int main() {

	int N,K;

	scanf("%d",&N);

	sumans=0;

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

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

		sumans+=a[i];

		tong[a[i]]+=1;

	}

	scanf("%d",&K);

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

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

		sumans-=1ll*tong[b]*b;

		sumans+=1ll*tong[b]*c;

		

		tong[c]+=tong[b];

		tong[b]=0;

		

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

	}

	

	return 0;

}