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

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn=2e5+100;

typedef long long LL;

int n;

LL a[maxn],p[5];



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

{

    while (scanf("%d",&n)!=EOF)

    {

        memset(a,0,sizeof(a));

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

        {

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

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

        }



        LL ans=3e14;

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

        {

            int x=lower_bound(a+1,a+i+1,a[i]/2)-a;

            int y=lower_bound(a+1,a+n+1,a[i]+(a[n]-a[i])/2)-a;

            if (x!=1) x--;

            if (y!=i+1) y--;



            p[0]=a[x];

            p[1]=a[i]-a[x];

            p[2]=a[y]-a[i];

            p[3]=a[n]-a[y];

            ans=min(ans,abs(max(p[0],max(p[1],max(p[2],p[3])))-min(p[0],min(p[1],min(p[2],p[3])))));



            int x1=x+1,y1=y;

            p[0]=a[x1];

            p[1]=a[i]-a[x1];

            p[2]=a[y1]-a[i];

            p[3]=a[n]-a[y1];

            ans=min(ans,abs(max(p[0],max(p[1],max(p[2],p[3])))-min(p[0],min(p[1],min(p[2],p[3])))));



            int x2=x,y2=y+1;

            p[0]=a[x2];

            p[1]=a[i]-a[x2];

            p[2]=a[y2]-a[i];

            p[3]=a[n]-a[y2];

            ans=min(ans,abs(max(p[0],max(p[1],max(p[2],p[3])))-min(p[0],min(p[1],min(p[2],p[3])))));



            int x3=x+1,y3=y+1;

            p[0]=a[x3];

            p[1]=a[i]-a[x3];

            p[2]=a[y3]-a[i];

            p[3]=a[n]-a[y3];

            ans=min(ans,abs(max(p[0],max(p[1],max(p[2],p[3])))-min(p[0],min(p[1],min(p[2],p[3])))));

        }

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

    }

    return 0;

}


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

#define PI acos(-1.0)

#define pb push_back

#define F first

#define S second

using namespace std;

typedef long long ll;

const int N=2e5+5;

const int MOD=1e9+7;

ll a[N];

ll sum[N];

//ll ans[N];

 

ll gao(int l,int r){  //求区间l,r的和

    return sum[r]-sum[l-1];

}

 

int main(void){

    ios::sync_with_stdio(false);

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

 

    int n ;

    cin >>n;

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

    for(int i=1;i<=n;i++)   sum[i]=sum[i-1]+a[i]; //求前缀和

    ll l=1,r=3;

    ll ans=1e18+8;

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

         while(l+1<i&&abs(gao(1,l)-gao(l+1,i))>=abs(gao(1,l+1)-gao(l+2,i)))//若[1,l+1]和[l+1,i]的距离比[1,l+1]和[l+2,i]的距离小，那么我们就继续加，使得两边尽可能平衡

            l++;

         while(r+1<n&&abs(gao(i+1,r)-gao(r+1,n))>=abs(gao(i+1,r+1)-gao(r+2,n)))

            r++;

         set<ll>st;///利用set的log排序

         st.insert(gao(1,l));

         st.insert(gao(l+1,i));

         st.insert(gao(i+1,r));

         st.insert(gao(r+1,n));

         ans=min(ans,abs(*st.begin()-*prev(st.end())));

    }

    cout << ans << endl;

 

    return 0;

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

#include <vector>

#include <algorithm>

 

using namespace std;

typedef long long ll;

 

int main() {

  int N;

  cin >> N;

  vector<ll> A(N);

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

    cin >> A[i];

  }

  vector<ll> acc(N + 1);

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

    acc[i + 1] = acc[i] + A[i];

  }



  ll ans = 1LL << 62;

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

    int i1 = lower_bound(acc.begin(), acc.begin() + j, acc[j] / 2) - acc.begin();

    int i2 = i1 - 1;

    int k1 = lower_bound(acc.begin() + j, acc.end(), (acc[N] - acc[j]) / 2 + acc[j]) - acc.begin();

    int k2 = k1 - 1;

    vector<int> I = {i1}, K = {k1};

    if (i2 > 0) I.push_back(i2);

    if (k2 > j) K.push_back(k2);

    for(int ii = 0; ii < I.size(); ii++) {

      for(int kk = 0; kk < K.size(); kk++) {

        int i = I[ii], k = K[kk];

        vector<ll> area;

        area.push_back(acc[i]);

        area.push_back(acc[j] - acc[i]);

        area.push_back(acc[k] - acc[j]);

        area.push_back(acc[N] - acc[k]);

        sort(area.begin(), area.end());

        ans = min(ans, area.back() - area[0]);

      }

    }

  }

  cout << ans << endl;

  return 0;

}

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

#include <algorithm>



using namespace std;

typedef long long ll;



int N;

ll A[200001];

ll acc[200002];



int main() {

    scanf("%d", &N);

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

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

    }

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

        acc[i + 1] = acc[i] + A[i];

    }

    ll ans = 1LL << 62;

    int i = 1, k = 3;

    for(int j = 2; j < N - 1; j++) {

        while(i + 1 < j) {

            ll newarea = acc[i + 1] - acc[0];

            ll area = acc[i] - acc[0];

            if (abs(newarea - (acc[j] - newarea)) > abs(area - (acc[j] - area))) break;

            i++;

        }

        while(k + 1 < N) {

            ll newarea = acc[k + 1] - acc[j];

            ll area = acc[k] - acc[j];

            if (abs(newarea - (acc[N] - acc[j] - newarea)) > abs(area - (acc[N] - acc[j] - area))) break;

            k++;

        }

        ll mi = min(min(acc[i], acc[j] - acc[i]), min(acc[k] - acc[j], acc[N] - acc[k]));

        ll ma = max(max(acc[i], acc[j] - acc[i]), max(acc[k] - acc[j], acc[N] - acc[k]));        

        ans = min(ans, ma - mi);

    }

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

    return 0;

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



using namespace std;



#define pb push_back

#define mp make_pair

constexpr int INF = 1 << 29;

constexpr int MOD = 1000000007;

typedef long long ll;

typedef unsigned long long ull;



constexpr int dx[4] = {1, 0, -1, 0};

constexpr int dy[4] = {0, 1, 0, -1};



int main() {

    int N;

    cin >> N;

    vector<ll> A(N);

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

        cin >> A[i];

    }

    vector<ll> acc(N + 1);

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

        acc[i + 1] = acc[i] + A[i];

    }

    ll ans = 1LL << 62;

    int i = 1, k = 3;

    for(int j = 2; j < N - 1; j++) {

        while(i + 1 < j) {

            ll newarea = acc[i + 1] - acc[0];

            ll area = acc[i] - acc[0];

            if (abs(newarea - (acc[j] - newarea)) > abs(area - (acc[j] - area))) break;

            i++;

        }

        while(k + 1 < N) {

            ll newarea = acc[k + 1] - acc[j];

            ll area = acc[k] - acc[j];

            if (abs(newarea - (acc[N] - acc[j] - newarea)) > abs(area - (acc[N] - acc[j] - area))) break;

            k++;

        }

        vector<ll> area;

        area.push_back(acc[i]);

        area.push_back(acc[j] - acc[i]);

        area.push_back(acc[k] - acc[j]);

        area.push_back(acc[N] - acc[k]);

        sort(area.begin(), area.end());

        ans = min(ans, area.back() - area[0]);

    }

    cout << ans << endl;

    return 0;

}


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

#include <algorithm>



using namespace std;

typedef long long ll;



int N;

ll A[200001];

ll acc[200002];



int main() {

    scanf("%d", &N);

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

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

    }

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

        acc[i + 1] = acc[i] + A[i];

    }

    ll ans = 1LL << 62;

    int i = 1, k = 3;

    for(int j = 2; j < N - 1; j++) {

        while(i + 1 < j) {

            ll newarea = acc[i + 1] - acc[0];

            ll area = acc[i] - acc[0];

            if (abs(newarea - (acc[j] - newarea)) > abs(area - (acc[j] - area))) break;

            i++;

        }

        while(k + 1 < N) {

            ll newarea = acc[k + 1] - acc[j];

            ll area = acc[k] - acc[j];

            if (abs(newarea - (acc[N] - acc[j] - newarea)) > abs(area - (acc[N] - acc[j] - area))) break;

            k++;

        }

        ll mi = min(min(acc[i], acc[j] - acc[i]), min(acc[k] - acc[j], acc[N] - acc[k]));

        ll ma = max(max(acc[i], acc[j] - acc[i]), max(acc[k] - acc[j], acc[N] - acc[k]));        

        ans = min(ans, ma - mi);

    }

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

    return 0;

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



using namespace std;



#define pb push_back

#define mp make_pair

constexpr int INF = 1 << 29;

constexpr int MOD = 1000000007;

typedef long long ll;

typedef unsigned long long ull;



constexpr int dx[4] = {1, 0, -1, 0};

constexpr int dy[4] = {0, 1, 0, -1};



int main() {

    int N;

    scanf("%d", &N);

    vector<ll> A(N);

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

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

    }

    vector<ll> acc(N + 1);

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

        acc[i + 1] = acc[i] + A[i];

    }

    ll ans = 1LL << 62;

    int i = 1, k = 3;

    for(int j = 2; j < N - 1; j++) {

        while(i + 1 < j) {

            ll newarea = acc[i + 1] - acc[0];

            ll area = acc[i] - acc[0];

            if (abs(newarea - (acc[j] - newarea)) > abs(area - (acc[j] - area))) break;

            i++;

        }

        while(k + 1 < N) {

            ll newarea = acc[k + 1] - acc[j];

            ll area = acc[k] - acc[j];

            if (abs(newarea - (acc[N] - acc[j] - newarea)) > abs(area - (acc[N] - acc[j] - area))) break;

            k++;

        }

        vector<ll> area;

        area.push_back(acc[i]);

        area.push_back(acc[j] - acc[i]);

        area.push_back(acc[k] - acc[j]);

        area.push_back(acc[N] - acc[k]);

        sort(area.begin(), area.end());

        ans = min(ans, area.back() - area[0]);

    }

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

    return 0;

}


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

#include <algorithm>



using namespace std;

typedef long long ll;



int N;

ll A[200001];

ll acc[200002];



int main() {

    scanf("%d", &N);

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

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

    }

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

        acc[i + 1] = acc[i] + A[i];

    }

    ll ans = 1LL << 62;

    int i = 1, k = 3;

    for(int j = 2; j < N - 1; j++) {

        while(i + 1 < j) {

            ll newarea = acc[i + 1] - acc[0];

            ll area = acc[i] - acc[0];

            if (abs(newarea - (acc[j] - newarea)) > abs(area - (acc[j] - area))) break;

            i++;

        }

        while(k + 1 < N) {

            ll newarea = acc[k + 1] - acc[j];

            ll area = acc[k] - acc[j];

            if (abs(newarea - (acc[N] - acc[j] - newarea)) > abs(area - (acc[N] - acc[j] - area))) break;

            k++;

        }

        ll mi = min(min(acc[i], acc[j] - acc[i]), min(acc[k] - acc[j], acc[N] - acc[k]));

        ll ma = max(max(acc[i], acc[j] - acc[i]), max(acc[k] - acc[j], acc[N] - acc[k]));        

        ans = min(ans, ma - mi);

    }

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

    return 0;

}
// Slower C++ solution:
#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);

}

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

}
// Slower C++ solution:
#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;

}

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

}
// Slower C++ solution:
#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;

}

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

}
// Slower C++ solution:
#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);

}

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

}
// Slower C++ solution:
#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);

}

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

}
// Slower C++ solution:
#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;

}


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

}