stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<iostream>

#include<cstdio>

using namespace std;

long long s1[200010],s2[200010];

int n,m;

long long all;

int nw;

long long ans=1e18;

int main()

{

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

	nw--;

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

	{

		int x;

		scanf("%d",&x);

		x--;

		nw%=m;

		if(x<nw)x+=m;

		all+=x-nw;

		s1[nw+1]++;

		s1[x+1]--;

		s2[nw+1]+=nw;

		s2[x+1]-=nw;

		nw=x;

	}

	for(int i=1;i<2*m;i++)

	{

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

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

	}

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

	{

		long long a=s1[i],b=s2[i];

		long long t=all;

		t-=(long long)i*a-b-a;

		a=s1[i+m],b=s2[i+m];

		t-=(long long)(i+m)*a-b-a;

		ans=min(ans,t);

	}

	printf("%lld",ans);

	return 0;

} 

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

#include<algorithm>

using namespace std;

#define ll long long

const int maxn=1e5+5;

const ll INF=0x3f3f3f3f3f3f3f3f;

int a[maxn];

struct node

{

    int l,r;

    ll diff,lz;

}tree[4*maxn];

void build(int l,int r,int cur)

{

    tree[cur].l=l;

    tree[cur].r=r;

    if(l==r)

        return;

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

    build(l,mid,cur<<1);

    build(mid+1,r,cur<<1|1);

    return;

}

void push_up(int cur)

{

    tree[cur].diff=tree[cur<<1].diff+tree[cur<<1|1].diff;

    return;

}

void push_down(int cur)

{

    if(tree[cur].lz!=0)

    {

        tree[cur<<1].diff+=(tree[cur<<1].r-tree[cur<<1].l+1)*tree[cur].lz;

        tree[cur<<1].lz+=tree[cur].lz;

        tree[cur<<1|1].diff+=(tree[cur<<1|1].r-tree[cur<<1|1].l+1)*tree[cur].lz;

        tree[cur<<1|1].lz+=tree[cur].lz;

        tree[cur].lz=0;

    }

    return;

}

void add(int l,int r,ll val,int cur)

{

    if(l>r) return;

    if(tree[cur].l>=l&&tree[cur].r<=r)

    {

        tree[cur].diff+=(tree[cur].r-tree[cur].l+1)*val;

        tree[cur].lz+=val;

        return;

    }

    if(tree[cur].l>r||tree[cur].r<l)

        return;

    push_down(cur);

    add(l,r,val,cur<<1);

    add(l,r,val,cur<<1|1);

    push_up(cur);

    return;

}

ll diff0[maxn];

void together(int cur)

{

    if(tree[cur].l==tree[cur].r)

    {

        diff0[tree[cur].l]=tree[cur].diff;

        return;

    }

    push_down(cur);

    together(cur<<1);

    together(cur<<1|1);

    push_up(cur);

    return;

}

ll minn[maxn];

int main()

{

    int n,m;

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

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

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

    build(0,m-1,1);

    ll base=0;

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

    {

        if(a[i]<a[i+1])

        {

            base+=(ll)(a[i+1]-a[i]);

            add(a[i]+1,a[i+1]-1,-1,1);

            add(a[i+1],a[i+1],a[i+1]-a[i]-1,1);

        }

        else

        {

            base+=(ll)(m-a[i]+a[i+1]);

            add(0,0,-(m-a[i]),1);

            add(1,a[i+1]-1,-1,1);

            add(a[i+1],a[i+1],m-a[i]+a[i+1]-1,1);

            add(a[i]+1,m-1,-1,1);

        }

    }

    together(1);

    minn[0]=base;

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

        minn[i]=minn[i-1]+diff0[i-1];

    ll ans=INF;

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

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

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

    return 0;

}

/*

 4 6

 1 5 1 4

 8 9 7 5 6 9

 

 9 9 8 7 6 5 4 3 2

 */
// Slower C++ solution:
#include "bits/stdc++.h"

using namespace std;

typedef long long ll;

typedef pair<ll, ll> P;

typedef pair<ll, P>IP;

typedef vector<ll> V;

typedef vector<V> V2;

typedef vector<vector<P> > G;

void g_dir(G &graph, ll a, ll b, ll w = 1){graph[a].push_back(P(b, w));}

void g_undir(G &graph, ll a, ll b, ll w = 1){g_dir(graph, a, b, w);g_dir(graph, b, a, w);}

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

#define rep1(i, n) for(ll (i) = 1; (i) <= (n); (i)++)

#define rrep(i, n) for(ll (i) = (n) - 1; (i) >= 0; (i)--)

#define rrep1(i, n) for(ll (i) = (n); (i) >= 1; (i)--)

template<class T> void chmax(T &a, const T &b){if(a < b){a = b;}}

template<class T> void chmin(T &a, const T &b){if(a > b){a = b;}}

const ll INF = 1145141919;

const ll MOD = 1000000007;

const ll NUM = 101010;



ll cnt[202020];



int main(){



    ll N, M;

    cin >> N >> M;

    V v(N);

    rep(i, N)cin >> v[i];

    ll sum = 0;

    rep(i, N - 1){

        ll a = v[i], b = v[i + 1];

        if(a > b)b += M;

        cnt[a + 2]++;

        cnt[b + 1]--;

        sum += b - a;

    }

    rep1(i, 202000)cnt[i] += cnt[i - 1];

    rep(i, N - 1){

        ll a = v[i], b = v[i + 1];

        if(a > b)b += M;

        cnt[b + 1] -= b - a - 1;

    }

    rep1(i, 202000)cnt[i] += cnt[i - 1];

    // cout << sum << endl;

    // rep1(i, 2 * M)cout << i << " : " << cnt[i] << endl;

    ll ans = sum;

    rep1(i, M)chmin(ans, sum - cnt[i] - cnt[i + M]);

    cout << ans << endl;



    return 0;

}

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

using namespace std;

typedef long long ll;

typedef pair<ll, ll> P;

typedef pair<ll, P>IP;

typedef vector<ll> V;

typedef vector<V> V2;

typedef vector<vector<P> > G;

void g_dir(G &graph, ll a, ll b, ll w = 1){graph[a].push_back(P(b, w));}

void g_undir(G &graph, ll a, ll b, ll w = 1){g_dir(graph, a, b, w);g_dir(graph, b, a, w);}

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

#define rep1(i, n) for(ll (i) = 1; (i) <= (n); (i)++)

#define rrep(i, n) for(ll (i) = (n) - 1; (i) >= 0; (i)--)

#define rrep1(i, n) for(ll (i) = (n); (i) >= 1; (i)--)

template<class T> void chmax(T &a, const T &b){if(a < b){a = b;}}

template<class T> void chmin(T &a, const T &b){if(a > b){a = b;}}

const ll INF = 1145141919;

const ll MOD = 1000000007;

const ll NUM = 101010;



void ruiseki_inc(V &v, vector<P>&p){

    rep(i, v.size())v[i] = 0;

    rep(i, p.size()){

        v[p[i].first]++;

        v[p[i].second + 1]--;

    }

    rep(i, v.size() - 1)v[i + 1] += v[i];

    rep(i, p.size()){

        v[p[i].second + 1]-=p[i].second - p[i].first + 1;

    }

    rep(i, v.size() - 1)v[i + 1] += v[i];

}



int main(){



    ll N, M;

    cin >> N >> M;

    V a(N);

    rep(i, N)cin >> a[i];

    ll sum = 0;

    V v(2 * M + 10, 0);

    vector<P>p;

    rep(i, N - 1){

        ll x = a[i], y = a[i + 1];

        if(x > y)y += M;

        sum += y - x;

        p.push_back(P(x + 2, y));                

    }

    ruiseki_inc(v, p);

    ll ans = sum;

    rep1(i, M)chmin(ans, sum - v[i] - v[i + M]);

    cout << ans << endl;



    return 0;

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

#include<algorithm>

#include<string>

#include<vector>

#include<queue>

#include<cmath>

using namespace std;



long long n, m, a[300009], c, p[300009];

int main() {

	cin >> n >> m;

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

	for (int i = 1; i <= n - 1; i++) { c += (a[i + 1] - a[i] + m) % m; }

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

		long long L = a[i] + 2, R = a[i + 1] + 1;

		if (L > R)R += m;

		if ((a[i + 1] - a[i] + m) % m < 2)continue;

		p[L]++; p[R] -= (R - L + 1); p[R + 1] += (R - L);

	}

	for (int i = 1; i <= 300000; i++)p[i] += p[i - 1];

	for (int i = 1; i <= 300000; i++)p[i] += p[i - 1];

	long long maxn = 0;

	for (int i = 1; i <= m; i++)maxn = max(maxn, p[i] + p[i + m] + p[i + m + m]);

	cout << c - maxn << endl;

	return 0;

}

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

#include <algorithm>

using namespace std;



long long n, m, a[100009], p[200009], v;



int main() {

	cin >> n >> m;

	for (int i = 1; i <= n; i++) { cin >> a[i]; if (i >= 2) { v += (a[i] - a[i - 1] + m) % m; } }

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

		if ((a[i + 1] - a[i] + m) % m <= 1) continue;

		int L = a[i] + 2, R = a[i + 1] + 1; if (L > R) R += m;

		p[L]++; p[R] -= (R - L + 1); p[R + 1] += (R - L);

	}

	for (int i = 1; i <= 2 * m; i++) p[i] += p[i - 1];

	for (int i = 1; i <= 2 * m; i++) p[i] += p[i - 1];

	

	long long maxn = 0;

	for (int i = 1; i <= m; i++) maxn = max(maxn, p[i] + p[i + m]);

	cout << v - maxn << endl;

	return 0;

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

#include<algorithm>

#include<string>

#include<vector>

#include<queue>

#include<cmath>

using namespace std;



long long n, m, a[300009], c, p[300009];

int main() {

	cin >> n >> m;

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

	for (int i = 1; i <= n - 1; i++) { c += (a[i + 1] - a[i] + m) % m; }

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

		long long L = a[i] + 2, R = a[i + 1] + 1;

		if (L > R)R += m;

		if ((a[i + 1] - a[i] + m) % m < 2)continue;

		p[L]++; p[R] -= (R - L + 1); p[R + 1] += (R - L);

	}

	for (int i = 1; i <= 300000; i++)p[i] += p[i - 1];

	for (int i = 1; i <= 300000; i++)p[i] += p[i - 1];

	long long maxn = 0;

	for (int i = 1; i <= m; i++)maxn = max(maxn, p[i] + p[i + m] + p[i + m + m]);

	cout << c - maxn << endl;

	return 0;

}

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

#include <algorithm>

using namespace std;



long long n, m, a[100008], p[200009], sum = 0, maxn = 0;



int main() {

	cin >> n >> m;

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

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

		long long L = a[i], R = a[i + 1]; if (L > R) R += m; sum += (R - L);

		if (R - L <= 1) continue;

		p[L + 2]++;

		p[R + 1] -= (R - L);

		p[R + 2] += (R - L - 1);

	}

	for (int i = 1; i <= 2 * m + 1; i++) p[i] += p[i - 1];

	for (int i = 1; i <= 2 * m + 1; i++) p[i] += p[i - 1];

	long long maxn = 0;

	for (int i = 1; i <= m; i++) maxn = max(maxn, p[i] + p[i + m]);

	cout << sum - maxn << endl;

	return 0;

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

using namespace std;

typedef long long ll;

const int N = 1 << 17;

struct Segt {

	ll sum[N << 1], add[N << 1];

	Segt() {

		memset(sum, 0, sizeof sum);

		memset(add, 0, sizeof add);

	}

	void pd(int i, int l) {

		if (add[i]) {

			sum[i] += add[i] * l;

			if (i < N) {

				add[i + i] += add[i];

				add[i + i + 1] += add[i];

			}

			add[i] = 0;

		}

	}

	void upd(int i, int a, int b, int l, int r, int v) {

		if (l <= a && b <= r) {

			add[i] += v;

			pd(i, b - a); return;

		}

		pd(i, b - a);

		if (r <= a || b <= l) return;

		int md = (a + b) >> 1;

		upd(i + i, a, md, l, r, v);

		upd(i + i + 1, md, b, l, r, v);

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

	}

	ll qry(int i, int a, int b, int l, int r) {

		pd(i, b - a);

		if (l <= a && b <= r) return sum[i];

		if (r <= a || b <= l) return 0;

		int md = (a + b) >> 1;

		ll L = qry(i + i, a, md, l, r);

		ll R = qry(i + i + 1, md, b, l, r);

		return L + R;

	}

} segt;

int n, m;

int a[N];

int main() {

	ios :: sync_with_stdio(0);

	cin >> n >> m;

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

	ll tot = 0;

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

		if (a[i] < a[i + 1]) {

			tot += a[i + 1] - a[i];

			segt.upd(1, 0, N, a[i] + 2, a[i + 1] + 1, 1);

			segt.upd(1, 0, N, a[i + 1] + 1, a[i + 1] + 2, -(a[i + 1] - a[i] - 1));

		} else {

			tot += m - a[i] + a[i + 1];

			segt.upd(1, 0, N, a[i] + 2, m, 1);

			segt.upd(1, 0, N, 0, 1, m - a[i] - 1);

			segt.upd(1, 0, N, 1, a[i + 1] + 1, 1);

			segt.upd(1, 0, N, a[i + 1] + 1, a[i + 1] + 2, -(m - a[i] + a[i + 1] - 1));

		}

//		for (int j = 0; j < m; ++ j) cerr << segt.qry(1, 0, N, 0, j + 1) << " "; cerr << endl;

	}

	cerr << tot << endl;

	ll mx = 0;

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

		ll cur = segt.qry(1, 0, N, 0, i + 1);

//		cerr << i << ": " << cur << endl;

		mx = max(mx, cur);

	}

	cout << tot - mx << endl;

	return 0;

}

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

using namespace std;

#define reg register

#define ll long long

inline ll read()

{

	ll x=0,w=0;char ch=getchar();

	while(!isdigit(ch))w|=ch=='-',ch=getchar();

	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();

	return w?-x:x;

}

ll n,m,ans=1e15;

ll a[100005],b[100005];

int main()

{

    n=read(),m=read();reg int i;

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

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

    {

        if(a[i]<a[i-1])

        {

            b[a[i-1]+2]--;b[1]+=a[i],b[2]-=a[i];b[2]--;b[a[i]+2]++;b[a[i]+1]+=m-a[i-1]+a[i];b[a[i]+2]-=m-a[i-1]+a[i];

        }

        else

        {

            b[1]+=a[i]-a[i-1],b[2]-=a[i]-a[i-1];b[a[i-1]+2]--;b[a[i]+2]++;b[a[i]+1]+=a[i]-a[i-1];b[a[i]+2]-=a[i]-a[i-1];

        }

    }

    for(i=1;i<=m;++i)b[i]+=b[i-1];for(i=1;i<=m;++i)b[i]+=b[i-1];

    for(i=1;i<=m;++i)ans=min(ans,b[i]);cout<<ans<<"\n";

	return 0;

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

#include<utility>

#define MOD 1000000007

#define INF 0x3f3f3f3f

#define INFL 0x3f3f3f3f3f3f3f3f

#define EPS (1e-10)

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

using namespace std;

typedef long long ll;

typedef pair<int, int>P;

#define int long long



int a[100000], n, m;

ll sum[300000];

ll sum2[300000];

ll e[300000];

int dist(int a, int b) {

	return (b >= a ? b - a : b + m - a);

}

int dist(int a, int b, int c) {

	int A = dist(a, b), B = 1 + dist(c, b);

	return (A < B ? A : B);

}

signed main() {

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

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

	rep(i, n - 1) {

		if (a[i] < a[i + 1]) {

			sum[a[i] + 1]++;

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

			e[a[i + 1] + 1] -= a[i + 1] - a[i];

		}

		else {

			sum[a[i] + 1]++;

			sum[a[i + 1] + m + 1]--;

			e[a[i + 1] + m + 1] -= a[i + 1] + m - a[i];

		}

	}

	for (int i = 1; i <= 200005; i++)sum[i] += sum[i - 1];

	for (int i = 1; i <= 200005; i++)sum2[i] = sum2[i - 1] + e[i] + sum[i];

	ll id = 0, Max = 0;

	rep(i, m) {

		if (sum2[i] + sum2[i + m] > Max) {

			id = i; Max = sum2[i] + sum2[i + m];

		}

	}

	ll ans = 0;

	rep(i, n - 1) {

		ans += dist(a[i], a[i + 1], id);

	}

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

}

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

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

using namespace std;

typedef long long ll;



int a[100000], n, m;

ll sum[300000], sum2[300000];



int dist(int a, int b) {

	return (b + m - a) % m;

}

int dist(int a, int b, int c) {

	return min(dist(a, b), dist(c, b) + 1);

}

signed main() {

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

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

	rep(i, n - 1) {

		if (a[i] < a[i + 1]) {

			sum[a[i] + 1]++;

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

			sum2[a[i + 1] + 1] -= a[i + 1] - a[i];

		}

		else {

			sum[a[i] + 1]++;

			sum[a[i + 1] + m + 1]--;

			sum2[a[i + 1] + m + 1] -= a[i + 1] + m - a[i];

		}

	}

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

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

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

	}

	ll id = 0, Max = 0;

	rep(i, m) {

		if (sum2[i] + sum2[i + m] > Max) {

			id = i; Max = sum2[i] + sum2[i + m];

		}

	}

	ll ans = 0;

	rep(i, n - 1) {

		ans += dist(a[i], a[i + 1], id);

	}

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

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

#define ll long long

using namespace std;

const int N=100005;

int n,m;

ll ans,sum;

ll p[2*N];

int a[N];

int main()

{

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

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

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

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

		ll l=a[i],r=a[i+1];

		if(l>r)r+=m;

		sum+=r-l;

		if(r-l>1){

            p[l+2]+=1;

            p[r+1]-=r-l;

            p[r+2]+=r-l-1;

		}

	}

	for(int i=1;i<=2*m;i++)p[i]=p[i]+p[i-1];

	for(int i=1;i<=2*m;i++)p[i]=p[i]+p[i-1];

	ll ans=1e18;

	for(int i=1;i<=m;i++)ans=min(sum-p[i]-p[i+m],ans);

	printf("%lld",ans);

	return 0;

}

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

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

inline void read(ll &x){

    x=0;static char ch;static bool flag;flag = false;

    while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;

    while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;

}

#define rg register int

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

#define per(i,a,b) for(rg i=(a);i>=(b);--i)

const ll maxn = 100010;

ll a[maxn],d[maxn],n,m;

ll lazy[maxn<<2],tag[maxn<<2],num[maxn<<2];

void modify(ll rt,ll l,ll r,ll L,ll R,ll v){

    if(L <= l && r <= R){

        lazy[rt] += v;

        return ;

    }

    ll mid = l+r >> 1;

    if(L <= mid) modify(rt<<1,l,mid,L,R,v);

    if(R >  mid) modify(rt<<1|1,mid+1,r,L,R,v);

}

void insert(ll rt,ll l,ll r,ll L,ll R,ll s){

    if(L <= l && r <= R){

        tag[rt] += s;++ num[rt];

        return ;

    }

    ll mid = l+r >> 1;

    if(R <= mid) insert(rt<<1,l,mid,L,R,s);

    else if(L > mid) insert(rt<<1|1,mid+1,r,L,R,s);

    else{

        insert(rt<<1,l,mid,L,mid,(R-mid)+s);

        insert(rt<<1|1,mid+1,r,mid+1,R,s);

    }

}

ll res;

void query(ll rt,ll l,ll r,ll p){

    res += lazy[rt];

    res += tag[rt] + num[rt]*(r - p);

    if(l == r) return ;

    ll mid = l+r >> 1;

    if(p <= mid) query(rt<<1,l,mid,p);

    else query(rt<<1|1,mid+1,r,p);

}

int main(){

    read(n);read(m);

    rep(i,1,n){

        read(a[i]);

        if(i > 1){

            ll x = (a[i] - a[i-1] + m) % m;

            if(a[i] > a[i-1]){

                modify(1,1,m,1,a[i-1],x);

                if(a[i]+1 <= m) modify(1,1,m,a[i]+1,m,x);

                if(a[i-1]+1 <= a[i]) insert(1,1,m,a[i-1]+1,a[i],1);

            }else{

                modify(1,1,m,a[i]+1,a[i-1],x);

                insert(1,1,m,1,a[i],1);

                if(a[i-1]+1 <= m) insert(1,1,m,a[i-1]+1,m,a[i]+1);

            }

        }

    }

    ll ans = 1LL << 60;

    rep(i,1,m){

        res = 0;query(1,1,m,i);

        ans = min(ans,res);

    }

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

    return 0;

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

using namespace std;

int n,m,cnt,a[100010];

long long now,ans=1e18;

vector<int> v[100010],g[100010];

void add(int x)

{

	cnt+=v[x].size();

}

void del(int x)

{

	for (int i=0;i<g[x].size();i++)

	{

		int y=g[x][i];

		cnt--;

		int d=x-y;

		if (d<0)

		{

			d+=m;

		}

		now+=d-1;

	}

}

int main()

{

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

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

	{

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

	}

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

	{

		v[a[i]].push_back(a[i+1]);

		g[a[i+1]].push_back(a[i]);

		if (a[i]>a[i+1])

		{

			cnt++;

			now+=a[i+1];

		}

		else

		{

			now+=a[i+1]-a[i];

		}

	}

	ans=now;

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

	{

		del(i);

		now-=cnt;

		ans=min(ans,now);

		//cout<<i+1<<" "<<cnt<<" "<<now<<endl;

		add(i);

	}

	cout<<ans<<endl;

	return 0;

}


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



using namespace std ;



const int MAX = 1e5 + 10 ;



int arr[MAX] ;

int n , m ;

long long pref[2*MAX] , prefcnt[2*MAX] , Ans[2*MAX] ; 



int main()

{

	ios_base::sync_with_stdio(0) ;

	cin.tie(0) ;

	cin>>n>>m ;

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

	{

		cin>>arr[i] ;

		arr[i]-- ;

	}

	long long ans = 0ll ;

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

	{

		int dist = (arr[i+1] - arr[i] + m) % m ;

		ans += dist ;

		prefcnt[arr[i]+1]++ ;

		pref[arr[i]+dist+1] -= dist ;

		prefcnt[arr[i]+dist+1]-- ;

	}

	long long sum = 0 , cnt = 0 ;

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

	{

		cnt += prefcnt[i] ;

		sum += cnt ;

		sum += pref[i] ;

		Ans[i%m] -= max(0ll , sum-cnt) ;

	}

	long long x = *min_element(Ans , Ans + m) ;

	return cout<<ans+x<<"\n" , 0 ;

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

#include<string>

#include<algorithm>

#include<cstdlib>

template<typename T>

void fin(T const& t){ std::cout << t << std::endl; exit(0); }



int main() {

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

  std::string s; std::cin >> s;

  int ans = s.size();

  int aa[] = {0, 1, 0, 1};

  int bb[] = {0, -1, -1, 0};

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

    int a = aa[i], b = bb[i];

    int cur = a-b;

    for(auto c: s) {

      if(c=='0')      { --a; --b; }

      else if(c=='1') { ++a; ++b; }

      else            { --a; ++b; }

      if(a < 0) a += 2;

      if(b > 0) b -= 2;

      cur = std::max(cur, a-b);

    }

    ans = std::min(ans, cur);

  }

  fin(ans);

  return 0;

}


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

#include<algorithm>

char buf[1000010];

int main() {

  scanf("%s", buf);

  int a0 = 0, a1 = 1, b0 = 0, b1 = -1;

  int c0 = a0-b0, c1 = a0-b1, c2 = a1-b0, c3 = a1-b1;

  for(char *p = buf; *p; p++) {

    if(*p=='0')      { --a0; --a1; --b0; --b1; }

    else if(*p=='1') { ++a0; ++a1; ++b0; ++b1; }

    else             { --a0; --a1; ++b0; ++b1; }

    if(a0 < 0) a0 += 2;

    if(a1 < 0) a1 += 2;

    if(b0 > 0) b0 -= 2; 

    if(b1 > 0) b1 -= 2; 

    if(c0 < a0-b0) c0 = a0-b0;

    if(c1 < a0-b1) c1 = a0-b1;

    if(c2 < a1-b0) c2 = a1-b0;

    if(c3 < a1-b1) c3 = a1-b1;

  }

  if(c0 > c1) c0 = c1;

  if(c2 > c3) c2 = c3;

  if(c0 > c2) c0 = c2;

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

  return 0;

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

#include<string>

#include<algorithm>

#include<cstdlib>

template<typename T>

void fin(T const& t){ std::cout << t << std::endl; exit(0); }



int main() {

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

  std::string s; std::cin >> s;

  int a0 = 0, a1 = 1, b0 = 0, b1 = -1;

  int c0 = a0-b0, c1 = a0-b1, c2 = a1-b0, c3 = a1-b1;

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

    char c = s[i];

    if(c=='0')      { --a0; --a1; --b0; --b1; }

    else if(c=='1') { ++a0; ++a1; ++b0; ++b1; }

    else            { --a0; --a1; ++b0; ++b1; }

    if(a0 < 0) a0 += 2;

    if(b0 > 0) b0 -= 2;

    c0 = std::max(c0, a0-b0);

    c1 = std::max(c1, a0-b1);

    c2 = std::max(c2, a1-b0);

    c3 = std::max(c3, a1-b1);

    c = s[i+1];

    if(c=='0')      { --a0; --a1; --b0; --b1; }

    else if(c=='1') { ++a0; ++a1; ++b0; ++b1; }

    else            { --a0; --a1; ++b0; ++b1; }

    if(a1 < 0) a1 += 2;

    if(b1 > 0) b1 -= 2;

    c0 = std::max(c0, a0-b0);

    c1 = std::max(c1, a0-b1);

    c2 = std::max(c2, a1-b0);

    c3 = std::max(c3, a1-b1);

  }

  if(s.size()%2==1) {

    char c = s.back();

    if(c=='0')      { --a0; --a1; --b0; --b1; }

    else if(c=='1') { ++a0; ++a1; ++b0; ++b1; }

    else            { --a0; --a1; ++b0; ++b1; }

    if(a0 < 0) a0 += 2;

    if(b0 > 0) b0 -= 2;

    c0 = std::max(c0, a0-b0);

    c1 = std::max(c1, a0-b1);

    c2 = std::max(c2, a1-b0);

    c3 = std::max(c3, a1-b1);

  }

  fin(std::min(std::min(c0, c1), std::min(c2, c3)));

  return 0;

}




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

#include<algorithm>

char buf[1000010];

int main() {

  scanf("%s", buf);

  int a0 = 0, a1 = 1, b0 = 0, b1 = -1;

  int c0 = a0-b0, c1 = a0-b1, c2 = a1-b0, c3 = a1-b1;

  for(char *p = buf; *p; p++) {

    if(*p=='0')      { --a0; --a1; --b0; --b1; }

    else if(*p=='1') { ++a0; ++a1; ++b0; ++b1; }

    else             { --a0; --a1; ++b0; ++b1; }

    if(a0 < 0) a0 += 2;

    if(a1 < 0) a1 += 2;

    if(b0 > 0) b0 -= 2; 

    if(b1 > 0) b1 -= 2; 

    if(c0 < a0-b0) c0 = a0-b0;

    if(c1 < a0-b1) c1 = a0-b1;

    if(c2 < a1-b0) c2 = a1-b0;

    if(c3 < a1-b1) c3 = a1-b1;

  }

  if(c0 > c1) c0 = c1;

  if(c2 > c3) c2 = c3;

  if(c0 > c2) c0 = c2;

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

  return 0;

}