stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include<bits/stdc++.h>

#define N 100005

#define ll long long

using namespace std;

ll a[N],ans[N],mx;

int n,m,jdb[N];

int main(){

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

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

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

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

		jdb[i]=jdb[i-1];

		for (;a[i]+1ll*jdb[i]*m<a[i-1];jdb[i]++);

		a[i]+=1ll*jdb[i]*m;

	}

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

		int l=a[i-1]%m+1,r=a[i]%m;

		if (l!=m) ans[l+1]++;

		if (r!=m){

			ans[r+1]-=(m+r-l)%m+1;

			ans[r+2]+=(m+r-l)%m;

		}

		if (l>r){

			ans[1]+=m-l+1;

			ans[2]-=m-l;

		}

	}

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

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

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

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

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

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

#define N 100005

#define rep(i,j,k) for (ll i=j;i<=k;++i)

#define per(i,j,k) for (ll i=j;i>=k;--i)

using namespace std;

inline ll read(){

	char ch=getchar(); ll x=0,f=1;

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

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

	return x*f;

}

ll n,m,sum,ans,a[N],b[N],c[N];

int main(){

	n=read(); m=read();

	rep(i,1,n) a[i]=read();

	rep(i,1,n-1){

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

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

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

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

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

		}else{

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

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

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

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

		}

	}

	rep(i,1,m) b[i]+=b[i-1],c[i]+=c[i-1];

	rep(i,1,m) ans=max(ans,i*c[i]-b[i]);

	printf("%lld",sum-ans);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <iostream>

using namespace std;



typedef long long ll;

typedef pair<int, int> pii;



const int KN = 1e5 + 5;



int n, m, a[KN];

ll b[KN << 2];



int main() {

	ios::sync_with_stdio(false);

	cin >> n >> m;

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

		cin >> a[i];

	ll all = 0;

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

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

		if (l > r)

			r += m;

		all += r - l;

		if (l < r) {

			b[l + 1] += 1;

			b[r] -= (r - l + 1) - 1;

			b[r + 1] += (r - l + 1) - 2;

		}

	}

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

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

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

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

	ll ans = 1LL << 62;

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

		ans = min(ans, all - b[i] - b[i + m]);

	cout << ans << endl;

	return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

#define N 100005

#define rep(i,j,k) for (ll i=j;i<=k;++i)

#define per(i,j,k) for (ll i=j;i>=k;--i)

using namespace std;

inline ll read(){

	char ch=getchar(); ll x=0,f=1;

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

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

	return x*f;

}

ll n,m,sum,ans,a[N],b[N],c[N];

int main(){

	n=read(); m=read();

	rep(i,1,n) a[i]=read();

	rep(i,1,n-1){

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

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

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

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

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

		}else{

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

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

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

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

		}

	}

	rep(i,1,m) b[i]+=b[i-1],c[i]+=c[i-1];

	rep(i,1,m) ans=max(ans,i*c[i]-b[i]);

	printf("%lld",sum-ans);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<queue>

#include<cstdio>

#include<cstring>

#include<vector>

#include<algorithm>

using namespace std;

#define ll long long

#define N 100005

#define Abs(x) ((x) > 0 ? (x) : -(x))

#define Min(x,y) ((x) < (y) ? (x) : (y))

#define Max(x,y) ((x) > (y) ? (x) : (y))

inline ll read(){

	ll x = 0,f = 1;char ch = getchar();

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

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

	return x*f;

}



ll c[N],d[N];

ll a[N];

ll n,m,tot,to,Mx;

ll ans,all;



int main(){

	n = read(); m = read();

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

		ll x = read();

		if(i == 1 || x != a[tot])

			a[++tot] = x;

	}

	

	for(ll i = 2;i <= tot;i++){

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

		if(l > r) r += m;

		all += r-l;

		if(r-l > 1){

			d[l+2] += 1;

			d[r+1] -= (r-(l+2)+1)+1;

			d[r+2] += (r-(l+2)+1);

		} 

	}

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

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

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

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

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

		ans = max(ans,d[i]+d[i+m]);

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

	return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

#define N 100005

#define rep(i,j,k) for (ll i=j;i<=k;++i)

#define per(i,j,k) for (ll i=j;i>=k;--i)

using namespace std;

inline ll read(){

	char ch=getchar(); ll x=0,f=1;

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

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

	return x*f;

}

ll n,m,sum,ans,a[N],b[N],c[N];

int main(){

	n=read(); m=read();

	rep(i,1,n) a[i]=read();

	rep(i,1,n-1){

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

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

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

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

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

		}else{

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

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

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

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

		}

	}

	rep(i,1,m) b[i]+=b[i-1],c[i]+=c[i-1];

	rep(i,1,m) ans=max(ans,i*c[i]-b[i]);

	printf("%lld",sum-ans);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

#define ll long long

#define FOr(i,x,y)  for(ll i=x;i>=y;--i)

#define For(i,x,y)	for(ll i=x;i<=y;++i)

using namespace std;

namespace SHENZHEBEI{

#ifdef LOCAL

	struct szb{	szb(){	freopen("shenzhebei.in","r",stdin);	}	}shenzhebei;

#endif

#define NEG 1

	const int L=2333333;

	char SZB[L],*S=SZB,*T=SZB;

	inline char gc(){	if (S==T){	T=(S=SZB)+fread(SZB,1,L,stdin);	if (S==T) return '\n';	}	return *S++;	}

#if NEG

	inline ll readint(){	ll x=0,f=1;	char ch=gc();	for (;!isdigit(ch);ch=gc())	if (ch=='-') f=-1;	for (;isdigit(ch);ch=gc())	x=x*10-48+ch;	return x*f;	}

	inline void write(ll x){	if (x<0)	putchar('-'),x=-x;	if (x>=10)	write(x/10);	putchar(x%10+'0');	}

#else

	inline ll readint(){	ll x=0;	char ch=gc();	for (;!isdigit(ch);ch=gc());	for (;isdigit(ch);ch=gc())	x=x*10-48+ch;	return x;	}

	inline void write(ll x){	if (x>=10)	write(x/10);	putchar(x%10+'0');	}

#endif

	inline char readchar(){	char ch=gc();	for(;isspace(ch);ch=gc());	return ch;	}

	inline ll readstr(char *s){	char ch=gc();	int cur=0;	for(;isspace(ch);ch=gc());		for(;!isspace(ch);ch=gc())	s[cur++]=ch;	s[cur]='\0';	return cur;	}

	inline void writeln(ll x){	write(x);	puts("");	}

}using namespace SHENZHEBEI;

const ll N=200010;

ll n,m,a[N],ans,sum1[N],anst[N],sum2[N],answ;

ll calc(ll x,ll y){	return x>=y?x-y:(x+m-y);	}

int main(){

	n=readint();	m=readint();

	For(i,1,n)	a[i]=readint();

	For(i,2,n){

		ll t=calc(a[i],a[i-1]);

		ans+=calc(a[i],a[i-1]);

		if (t>=2){

			sum1[a[i-1]+2]++;

			sum1[a[i-1]+t+1]--;

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

		}

	}

	ll sum=0,sgr=0;

	For(i,1,2*m){

		sgr+=sum1[i];

		sum=sum+sgr+sum2[i];

		anst[i>m?i-m:i]+=sum;

	}answ=ans;

	For(i,1,m)	answ=min(answ,ans-anst[i]);

	writeln(answ);

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

#define N 100005

#define rep(i,j,k) for (ll i=j;i<=k;++i)

#define per(i,j,k) for (ll i=j;i>=k;--i)

using namespace std;

inline ll read(){

	char ch=getchar(); ll x=0,f=1;

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

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

	return x*f;

}

ll n,m,sum,ans,a[N],b[N],c[N];

int main(){

	n=read(); m=read();

	rep(i,1,n) a[i]=read();

	rep(i,1,n-1){

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

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

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

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

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

		}else{

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

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

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

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

		}

	}

	rep(i,1,m) b[i]+=b[i-1],c[i]+=c[i-1];

	rep(i,1,m) ans=max(ans,i*c[i]-b[i]);

	printf("%lld",sum-ans);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<cstdio>

#include<queue>

#include<cmath>

#include<algorithm>

#include<map>

#include<cstring>

#define For(i,j,k) for(ll i=j;i<=k;++i)

#define Dow(i,j,k) for(ll i=k;i>=j;--i)

#define ll long long

using namespace std;

inline ll read()

{

	ll t=0,f=1;char c=getchar();

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

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

	return t*f;

}

ll n,m,a[600001],f[600001];

inline void add(ll x,ll v){x++;for(;x<=(m+2);x+=x&-x)	f[x]+=v;}

inline ll get(ll x){x++;ll sum=0;for(;x;x-=x&-x)	sum+=f[x];return sum;}

inline void ADD(ll l,ll r,ll v){if(l>r)	return;add(l,v);add(r+1,-v);}

int main()

{

	n=read();m=read();

	For(i,1,n)

		a[i]=read();

	For(i,2,n)

	{

		if(a[i]>a[i-1])	{ADD(a[i-1]+2,a[i],1);ADD(a[i]+1,a[i]+1,-(a[i]-a[i-1]-1));}

		else

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

	}

	ll ans=0,sum=0,tot=0;

	For(i,1,m)

		tot+=get(i),ans=max(ans,tot);

	For(i,2,n)	

	{

		if(a[i]>a[i-1])	sum+=(a[i]-a[i-1]);

			else	sum+=(a[i]+(m-a[i-1]));

//		cout<<i<<"->"<<sum<<endl;

	}

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

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

#define N 100005

#define rep(i,j,k) for (ll i=j;i<=k;++i)

#define per(i,j,k) for (ll i=j;i>=k;--i)

using namespace std;

inline ll read(){

	char ch=getchar(); ll x=0,f=1;

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

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

	return x*f;

}

ll n,m,sum,ans,a[N],b[N],c[N];

int main(){

	n=read(); m=read();

	rep(i,1,n) a[i]=read();

	rep(i,1,n-1){

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

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

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

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

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

		}else{

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

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

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

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

		}

	}

	rep(i,1,m) b[i]+=b[i-1],c[i]+=c[i-1];

	rep(i,1,m) ans=max(ans,i*c[i]-b[i]);

	printf("%lld",sum-ans);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

#define N 200020

#define ll long long

using namespace std;

inline int read(){

	int x=0,f=1;char ch=getchar();

	while(ch>'9'||ch<'0')ch=='-'&&(f=0)||(ch=getchar());

	while(ch<='9'&&ch>='0')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return f?x:-x;

}

int a[N];

ll s1[N], s2[N], ans, res = 1ll << 60;

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

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

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

		a[i] = read();

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

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

		if (x > y) y += m;

		s1[x + 1] += x + 1;

		s1[y + 1] -= x + 1;

		s2[x + 1] ++;

		s2[y + 1] --;

	}

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

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

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

	}

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

		if (a[i] <= a[i + 1]) ans += a[i + 1] - a[i];

		else ans += a[i + 1] + m - a[i];

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

		res = min(res, ans - s2[i] * i - s2[i + m] * (i + m) + s1[i] + s1[i + m]);

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

	return 0;

}


// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

#define N 100005

#define rep(i,j,k) for (ll i=j;i<=k;++i)

#define per(i,j,k) for (ll i=j;i>=k;--i)

using namespace std;

inline ll read(){

	char ch=getchar(); ll x=0,f=1;

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

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

	return x*f;

}

ll n,m,sum,ans,a[N],b[N],c[N];

int main(){

	n=read(); m=read();

	rep(i,1,n) a[i]=read();

	rep(i,1,n-1){

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

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

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

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

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

		}else{

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

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

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

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

		}

	}

	rep(i,1,m) b[i]+=b[i-1],c[i]+=c[i-1];

	rep(i,1,m) ans=max(ans,i*c[i]-b[i]);

	printf("%lld",sum-ans);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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);

}

// Optimized solution to the same problem (faster):
#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);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}


// Optimized solution to the same problem (faster):
#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 ;

}		

// Fastest known solution for this problem: