Problem:
 Score : 700 points    Problem Statement Snuke is buying a lamp.
The light of the lamp can be adjusted to m levels of brightness, represented by integers from 1 through m , by the two buttons on the remote control.  The first button is a "forward" button. When this button is pressed, the brightness level is increased by 1 , except when the brightness level is m , in which case the brightness level becomes 1 .  The second button is a "favorite" button. When this button is pressed, the brightness level becomes the favorite brightness level x , which is set when the lamp is purchased.  Snuke is thinking of setting the favorite brightness level x so that he can efficiently adjust the brightness.
He is planning to change the brightness n-1 times. In the i -th change, the brightness level is changed from a_i to a_{i+1} . The initial brightness level is a_1 .
Find the number of times Snuke needs to press the buttons when x is set to minimize this number.      Constraints  2 \leq n,m \leq 10^5  1 \leq a_i\leq m  a_i \neq a_{i+1}  n , m and a_i are integers.         Input Input is given from Standard Input in the following format:  n  m  a_1  a_2 … a_n       Output Print the minimum number of times Snuke needs to press the buttons.        Sample Input 1 4 6
1 5 1 4      Sample Output 1 5  When the favorite brightness level is set to 1 , 2 , 3 , 4 , 5 and 6 , Snuke needs to press the buttons 8 , 9 , 7 , 5 , 6 and 9 times, respectively.
Thus, Snuke should set the favorite brightness level to 4 .
In this case, the brightness is adjusted as follows:   In the first change, press the favorite button once, then press the forward button once.  In the second change, press the forward button twice.  In the third change, press the favorite button once.        Sample Input 2 10 10
10 9 8 7 6 5 4 3 2 1      Sample Output 2 45

Solution (Python):

max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

N,M = map(int,input().split())
A = tuple(map(lambda x:int(x)-1,input().split()))

A = [a for a,b in zip(A,A[1:]) if a != b]+[A[-1]]


def it():
    events = [(a+1,-1) for a in A[:-1]] + [(a,p+1) for p,a in zip(A,A[1:])]
    events.sort()
    discount = 0
    cnt = 0
    for a,b in zip(A,A[1:]):
        discount += max2(0, (b-a)%M - 1 - b)
        cnt += int(b < a)
    yield discount
    last = 0
    for a,p in events:
        discount += (a-last)*cnt
        yield discount
        if p < 0:
            cnt += 1
        else:
            cnt -= 1
            discount -= (a-p)%M
        last = a

    yield discount

total = sum((b-a)%M for a,b in zip(A,A[1:]))
print(total - max(it()))

Solution (Python):
N, M = map(int, input().split())        
A = list(map(int, input().split()))
imos = [0]*(2*M+1)
imos2 = [0]*(2*M+1)
res = 0
for i in range(N-1):
    a, b =A[i]-1, A[i+1]-1
    if a>b: b += M
    res += b-a
    if a+2>=b+1:
        continue
    imos[a+2] += 1
    imos[b+1] -= 1
    imos2[b+1] -= (b-a-1)
P = [0]
l = 0
for k, s in zip(imos, imos2):
    l += k
    P.append(P[-1] + l + s)
Q = P[1:-1]
R = [x+y for x, y in zip(Q[:M],Q[M:])]
print(res - max(R))

Solution (Python):
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  


N,M = MI()
a = LI()

count = 0  
X = [0]*(2*M+1)
Y = [0]*(2*M+1)


for i in range(N-1):
    a0,a1 = a[i],a[i+1]
    count += (a1-a0) % M
    if a0 > a1:
        a1 += M
    if a0 == a1:
        continue
    X[a0+2] += 1
    X[a1+1] -= 1
    Y[a0+2] -= a0+1
    Y[a1+1] += a0+1

from itertools import accumulate

X = list(accumulate(X))
Y = list(accumulate(Y))

A = [0]*(M+1)
for i in range(1,M+1):
    A[i] = (X[i]*i+Y[i]) + (X[i+M]*(i+M)+Y[i+M])

print(count-max(A))

Solution (Python):
n,m = map(int,input().split())
a = list(map(int,input().split()))

imos = [0] * (2*m+2)
ans = 0
for i in range(n-1):
    a0 = a[i]-1
    a1 = a[i+1]-1
    dif = (a1-a0)%m
    ans += dif
    if(dif>=2):
        imos[a0+2] += 1
        imos[a0+dif+1] -= dif
        imos[a0+dif+2] += dif-1



for i in range(1,2*m+2):
    imos[i] += imos[i-1]


for i in range(1,2*m+2):
    imos[i] += imos[i-1]


for i in range(m):
    imos[i] += imos[i+m]

ans -= max(imos[:m])
print(ans)

Solution (Python):
n,m = map(int,input().split())
a = list(map(int,input().split()))

ex = [0] * m
left = [0] * (2*m)
right = [[0,0] for _ in range(2*m)]

ans = 0
for i in range(n-1):
    a0 = a[i]-1
    a1 = a[i+1]-1
    ans += (a1-a0)%m
    left[a0+1] += 1
    right[a1 + (a0>a1)*m][0] += 1
    right[a1 + (a0>a1)*m][1] += (a1-a0)%m -1

now = left[0]
dif = 0
for i in range(1,2*m):
    dif += now
    ex[i%m] -= dif
    now += left[i] - right[i][0]
    dif -= right[i][1]

ans += min(ex)
print(ans)

Solution (Python):
from itertools import accumulate
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
a = list(map(lambda x: int(x) - 1, input().split()))

cnt0 = [0] * m
cnt1 = [0] * m
for i in range(n-1):
    cnt0[a[i+1]] += (a[i+1] - a[i]) % m - 1
    if (a[i] + 1) % m <= a[i+1]:
        cnt1[(a[i]+1) % m] += 1
        cnt1[a[i+1]] -= 1
    else:
        cnt1[(a[i]+1) % m] += 1
        cnt1[0] += 1
        cnt1[a[i+1]] -= 1
cnt1 = list(accumulate(cnt1))
diff = list(accumulate([0] + [cnt0[i] - cnt1[i] for i in range(m-1)]))
ans = min(diff)
for i in range(n-1):
    ans += min((a[i+1] - a[i]) % m, a[i+1] + 1)
print(ans)

Solution (Python):
from itertools import accumulate
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
a = list(map(lambda x: int(x) - 1, input().split()))

cnt0 = [0] * m
cnt1 = [0] * m
for i in range(n-1):
    cnt0[a[i+1]] += (a[i+1] - a[i]) % m - 1
    if (a[i] + 1) % m <= a[i+1]:
        cnt1[(a[i]+1) % m] += 1
        cnt1[a[i+1]] -= 1
    else:
        cnt1[(a[i]+1) % m] += 1
        cnt1[0] += 1
        cnt1[a[i+1]] -= 1
cnt1 = list(accumulate(cnt1))
ans = float('inf')
tmp = 0
for i in range(n-1):
    tmp += min((a[i+1] - a[i]) % m, a[i+1] + 1)
ans = tmp
for i in range(m-1):
    tmp += cnt0[i] - cnt1[i]
    ans = min(ans, tmp)
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

class BIT:
    def __init__(self, size):
        self.bit = [0] * (size + 1)
        self.size = size

    def sum(self, i):
        i += 1
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.bit[i] += x
            i += i & -i

n, m = map(int, input().split())
a = list(map(lambda x: int(x) - 1, input().split()))

bit0 = BIT(m)
bit1 = BIT(m)
for i in range(n-1):
    x, y = a[i], a[i+1]
    bit1.add(0, (y - x) % m)
    if (y - x) % m < 2:
        continue
    x = (x + 2) % m
    if x <= y:
        bit0.add(x, -1)
        bit1.add(x, x - 1)
        bit0.add(y + 1, 1)
        bit1.add(y + 1, -(x - 1))
    else:
        bit0.add(x, -1)
        bit1.add(x, x - 1)

        b = (0 - (x - 1)) % m
        bit0.add(0, -1)
        bit1.add(0, -b)
        bit0.add(y + 1, 1)
        bit1.add(y + 1, b)

ans = min(bit0.sum(i) * i + bit1.sum(i) for i in range(m))
print(ans)

Solution (Python):
def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    N, M = LI()
    A = LI()
    S = [0]*(M+2)
    for i in range(N-1):
        a0, a1 = A[i:i+2]
        S[a0+1] += 1
        S[a1] -= 1
        if a1<a0:
            S[0] += 1
    
    for i in range(M):
        S[i+1] += S[i]
    for i in range(M+1):
        if S[i]<0:
            S[i] = 0
    D = defaultdict(int)
    for i in range(N-1):
        a0, a1 = A[i:i+2]
        cost = (a1 + M - a0) % M - 1
        D[a1] += cost
    start = 0
    for i in range(N-1):
        a0, a1 = A[i:i+2]
        cost = min(a1, (a1+M-a0)%M)
        start += cost
    
    
    
    cost = start
    ans = start
    for i in range(1,M):
        cost += (D[i] - S[i])
        
        if ans>cost:
            ans = cost
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Solution (Python):
"""
a(x-p) + b (p <= x <= q) の2階階差をとり、imos配列に加える
復元はaccumulateでやる
"""
def kaisa2_of_tousa(a,b,p,q,imos,n):
    if p > q: return
    imos[p] += b
    if p+1 < n: imos[p+1] += a-b
    y = a*(q-p)+b
    if q+1 < n: imos[q+1] += -y-a
    if q+2 < n: imos[q+2] += y



import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,m,*a = map(int,read().split())

imos = [0]*(2*m+1)
ans = 0
for p,q in zip(a,a[1:]):
    if p > q: q += m
    ans += q-p
    kaisa2_of_tousa(-1,0,p+1,q,imos,2*m+1)

from itertools import accumulate as acc
res = list(acc(acc(imos)))


v = 0
for i in range(1,m+1):
    w = res[i]+res[i+m]
    v = min(v,w)
    


print(ans+v)

Solution (Python):
n, m = map(int, input().split())
a = [int(x) for x in input().split()]
ps = [0]*(m+2)  

for i in range(n-1):
    if a[i] < a[i+1]:
        ps[a[i]+1] += 1
        ps[a[i+1]] -= 1
    else:
        ps[0] += 1
        ps[a[i+1]] -= 1
        ps[a[i]+1] += 1
        ps[m+1] -= 1

aps = [0]
for x in ps[:-1]:
    aps.append(aps[-1]+x)
aps = aps[2:]


def dist(src, tar):
    return (m+tar-src) % m


freq = [0]*m
for i, x in enumerate(a):
    if i == 0:
        continue
    freq[x-1] += dist(a[i-1], a[i])-1


ans = [0]*m
for i in range(n-1):
    ans[0] += min(dist(a[i], a[i+1]), 1+dist(1, a[i+1]))

for i in range(1, m):
    ans[i] = ans[i-1] + freq[i-1] - aps[i-1]

print(min(ans))

Solution (Python):
n,m=map(int,input().split())
arr=list(map(int,input().split()))
imos1=[0]*(m*2+2)
imos2=[0]*(m*2+2)
imos3=[0]*(m*2+2)
for i in range(n-1):
  cost=(m+arr[i+1]-arr[i])%m
  if arr[i]<arr[i+1]:
    imos1[arr[i]]+=cost
    imos1[arr[i]+m]-=cost
    imos2[arr[i]+2]+=-1
    imos2[arr[i+1]+1]+=1
    imos3[arr[i+1]+1]+=cost-1
  else:
    imos1[arr[i]]+=cost
    imos1[arr[i]+m]-=cost
    imos2[arr[i]+2]+=-1
    imos2[arr[i+1]+m+1]+=1
    imos3[arr[i+1]+m+1]+=cost-1
for i in range(1,m*2+2):
  imos2[i]+=imos2[i-1]
for i in range(m*2+2):
  imos1[i]+=imos2[i]
  imos1[i]+=imos3[i]
for i in range(1,m*2+2):
  imos1[i]+=imos1[i-1]
xs=[0]*(m+1)
xs[0]=10**18
for i in range(1,m+1):
  xs[i]=imos1[i]+imos1[m+i]
print(min(xs))

Solution (Python):
import sys
input = sys.stdin.readline
from itertools import accumulate

n, m = map(int, input().split())
A = list(map(int, input().split()))
L = [0]*(2*m)
B = []
cnt = 0
for i in range(n-1):
  a, b = A[i], A[i+1]
  a -= 1
  b -= 1
  if a < b:
    cnt += b-a
    if b-a == 1:
      continue
    L[a+2] += 1
    L[b+1] += -1
    B.append((b+1, -(b-a-1)))
  else:
    b += m
    cnt += b-a
    if b-a == 1:
      continue
    L[a+2] += 1
    L[b+1] += -1
    B.append((b+1, -(b-a-1)))
L = list(accumulate(L))
for i, b in B:
  L[i] += b
L = list(accumulate(L))
c = 0
for i in range(m):
  c = max(c, L[i]+L[m+i])
ans = cnt - c
print(ans)

Solution (Python):
n,m=map(int,input().split())
a=list(map(int,input().split()))
l=[0]*(m+2)
for i,j in zip(a,a[1:]):
    if j>i+1:
        l[j+1]-=1
        l[i+2]+=1
    elif i>j:
        if i<=m-2:
            l[i+2]+=1
            l[m+1]-=1
            l[1]+=1
            l[j+1]-=1
        else:
            l[i+2-m]+=1
            l[j+1]-=1
from itertools import accumulate
l=list(accumulate(l))
ans=0
l1=0
for i,j in zip(a,a[1:]):
    if j>i:
        ans+=j-i
        l[j+1]-=(j-i-1)
    else:
        l1+=m-i
        ans+=m+j-i
        l[j+1]-=(m+j-i-1)
l[1]=l1
l=list(accumulate(l))
print(ans-max(l[1:m+1]))

Solution (Python):
n,m=map(int,input().split())
a=list(map(int,input().split()))
a=[a[i]-1 for i in range(n)]

imos=[0 for i in range(m+1)]
for i in range(0,n-1):
    s,g=a[i],a[i+1]
    val=(g-s)%m
    if val>1:
        s=(s+2)%m
        if s>g:
            imos[s]+=-1
            imos[m]+=1
            imos[0]+=-1
            imos[g+1]+=1
        else:
            imos[s]+=-1
            imos[g+1]+=1
        imos[(g+1)%m]+=val-1
        imos[(g+1)%m+1]+=-(val-1)

for i in range(1,m+1):
    imos[i]+=imos[i-1]

for i in range(1,m+1):
    imos[i]+=imos[i-1]

ans=-1
val=0
for i in range(m):
    if val>=imos[i]:
        ans=i
        val=imos[i]

val=0
for i in range(0,n-1):
    s,g=a[i],a[i+1]
    if (g-s)%m>1:
        if g>=s:
            if g>=ans>s:
                val+=1+(g-ans)%m
            else:
                val+=(g-s)%m
        else:
            if ans>s or g>=ans:
                val+=1+(g-ans)%m
            else:
                val+=(g-s)%m
    else:
        val+=(g-s)%m


print(val)

Solution (Python):

class BIT():
    """区間加算、一点取得クエリをそれぞれO(logN)で答える
    add: 区間[l, r)にvalを加える
    get_val: i番目の値を求める
    i, l, rは0-indexed
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _add(self, i, val):
        while i > 0:
            self.bit[i] += val
            i -= i & -i

    def get_val(self, i):
        """i番目の値を求める"""
        i = i + 1
        s = 0
        while i <= self.n:
            s += self.bit[i]
            i += i & -i
        return s

    def add(self, l, r, val):
        """区間[l, r)にvalを加える"""
        self._add(r, val)
        self._add(l, -val)



n, m = map(int, input().split())
a = list(map(int, input().split()))

bit = BIT(2 * m + 10)
cnt = 0
for i in range(n - 1):
    l, r = a[i], a[i + 1]
    if l > r:
        r += m
    cnt += r - l
    if l == r or l + 1 == r:
        continue
    if l < r:
        l += 2
        r += 1
        bit.add(l, r, 1)
        bit.add(r, r + 1, -(r - l))
        continue

imos = [0] * (2 * m + 2)
for i in range(2 * m + 2):
    imos[i] += bit.get_val(i)
    if i - 1 >= 0:
        imos[i] += imos[i - 1]

ans = [0] * (m + 1)
for i in range(1, m + 1):
    ans[i] = imos[i] + imos[i + m]
print(cnt - max(ans))

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m = LI()
    a = LI()
    ans = sum([(a[i+1]-a[i])%m for i in range(n-1)])
    s = [0]*(2*m)
    f = [0]*(2*m)
    x = a[0]-1
    for i in range(1,n):
        y = a[i]-1
        if y < x:
            y += m
        if x+1 >= y:
            x = a[i]-1
            continue
        s[x+2] += 1
        s[y+1] -= 1
        f[y+1] -= y-x-1
        x = a[i]-1
    for i in range(2*m-1):
        s[i+1] += s[i]
        f[i+1] += f[i]+s[i+1]
    f = [f[i]+f[i+m] for i in range(m)]
    print(ans-max(f))
    return


if __name__ == "__main__":
    solve()

Solution (Python):
import sys
input = sys.stdin.readline
from heapq import *

n, m = map(int, input().split())
a = list(map(int, input().split()))
a = list(map(lambda x: x-1, a))
lr = []
cnt = 0

for i in range(n-1):
    ai, aj = a[i], a[i+1]
    
    if ai<aj:
        lr.append((ai+1, aj))
        cnt += aj-ai
    else:
        lr.append((ai-m+1, aj))
        lr.append((ai+1, m-1))
        cnt += m+aj-ai
    
lr.sort(key=lambda t: t[0])

idx = 0
ans = cnt
decre = 0
pq = []

for i in range(m):
    while len(pq)>0 and pq[0][0]<i:
        r, l = heappop(pq)
        
        decre -= r-l+1
        
    while idx<len(lr) and i>=lr[idx][0]:
        decre += i-lr[idx][0]
        
        heappush(pq, (lr[idx][1], lr[idx][0]))
        idx += 1
    
    ans = min(ans, cnt-decre)
    decre += len(pq)

print(ans)

Solution (Python):
def main():
    n, m = map(int, input().split())
    a = list(map(lambda x: int(x)-1, input().split()))
    event = [[] for _ in [0]*m]
    for j, i in enumerate(a):
        if j < n-1:
            A = m-a[j+1]
            if A < m:
                event[A].append((True, j))
        B = m-i
        if B < m:
            event[B].append((False, j))
    leader = 1
    now = a[-1]
    for i in range(n-1):
        if a[i] > a[i+1]:
            leader += 1
            now += a[i]
    s = a[0]
    ans = 10**20
    for i in range(m):
        for e, j in event[i]:
            if e:
                leader += 1
                now += ((a[j]+i) % m)
            else:
                now -= m
                if j != n-1:
                    leader -= 1
        now += leader
        ans = min(ans, now-1-(s+i) % m)
    print(ans)


main()

Solution (Python):
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
a = list(map(int, input().split()))
d = [0] * (N - 1)
imosa = [0] * (M * 2 + 2)
imosb = [0] * (M * 2 + 2)
for i in range(N - 1):
  if a[i + 1] >= a[i]:
    d[i] = a[i + 1] - a[i]
    imosa[a[i] + 1] += 1
    imosa[a[i + 1] + 1] -= 1
    imosb[a[i] + 1] -= a[i] + 1
    imosb[a[i + 1] + 1] += a[i] + 1
  else:
    d[i] = a[i + 1] + M - a[i]
    imosa[a[i] + 1] += 1
    imosa[a[i + 1] + M + 1] -= 1
    imosb[a[i] + 1] -= a[i] + 1
    imosb[a[i + 1] + M + 1] += a[i] + 1
  


imos = [0] * (M + 2)
for i in range(2 * M + 1):
  imosa[i + 1] += imosa[i]
  imosb[i + 1] += imosb[i]


for i in range(M + 2):
  imos[i] = imosa[i] * i + imosa[i + M] * (i + M) + imosb[i] + imosb[i + M]

print(sum(d) - max(imos[1: M + 1]))

Solution (Python):

"""
Writer: SPD_9X2
https://atcoder.jp/contests/arc077/tasks/arc077_c

お気に入りを決めてる時、その数字を超えるような移動が発生した場合だけ、ボタン2が有効になる。
ALLボタン１に比べて、何回節約できるかをimos法で計算する

"""

n,m = map(int,input().split())

lis = [0] * m

state = [0] * n

a = list(map(int,input().split()))
for i in range(n):
    a[i] -= 1

start = [ [] for i in range(m) ]
end = [ [] for i in range(m)]

allsum = 0
for i in range(n-1):

    allsum += (a[i+1]-a[i]) % m
    if a[i+1] == (a[i]+1)%m:
        continue

    start[(a[i]+1) % m].append(i)
    end[a[i+1] % m].append(i)

    


imosnum = 0
plus = 0



for i in range(2*m):

    plus += imosnum

    lis[i%m] += plus

    for j in end[i%m]:
        if state[j] == 1:
            plus -= ((a[j+1]-(a[j]+1))%m)
            state[j] = 2
            imosnum -= 1

    for j in start[i%m]:
        if state[j] == 0:
            imosnum += 1
            state[j] = 1

    

if (allsum - max(lis) < 0):
    print (asxacscd)

print (allsum - max(lis))

Solution (Python):
import sys
from itertools import accumulate
input = sys.stdin.readline
n,m = map(int,input().split())
a = list(map(int,input().split()))
ls_0 = [0 for i in range(m*2+2)]
ans_0 = 0
for i in range(1,n):
  if a[i-1] < a[i]:
    l = a[i-1]+2
    r = a[i]+1
  else:
    l = a[i-1]+2
    r = a[i]+m+1
  ls_0[l] += 1
  ls_0[r] -= (r-l+1)
  ls_0[r+1] += r-l
  ans_0 += r-l+1

ls_1 = list(accumulate(ls_0))
ls_2 = list(accumulate(ls_1))
ls_3 = [0]+[ls_2[i]+ls_2[i+m] for i in range(1,m+1)]
print(ans_0-max(ls_3))

Solution (Python):
from itertools import accumulate
n,m = map(int,input().split())
a = list(map(int,input().split()))
ls_0 = [0 for i in range(m*2+2)]
ans_0 = 0
for i in range(1,n):
  if a[i-1] < a[i]:
    l = a[i-1]+2
    r = a[i]+1
  else:
    l = a[i-1]+2
    r = a[i]+m+1
  ls_0[l] += 1
  ls_0[r] -= (r-l+1)
  ls_0[r+1] += r-l
  ans_0 += r-l+1

ls_1 = list(accumulate(ls_0))
ls_2 = list(accumulate(ls_1))
ls_3 = [0]+[ls_2[i]+ls_2[i+m] for i in range(1,m+1)]
print(ans_0-max(ls_3))

Solution (Python):
N, M = map(int, input().split())
As = list(map(int, input().split()))

ans = 0
numSts, numEns, sumEns = [0]*(2*M), [0]*(2*M), [0]*(2*M)
for i in range(N-1):
    A, B = As[i]-1, As[i+1]-1
    if A > B:
        B += M
    ans += B-A
    if B-A > 1:
        numSts[A+2] += 1
        numEns[B+1] += 1
        sumEns[B+1] += B-A-1

nums = [0]*M
num = 0
k = 0
for i in range(2*M):
    k += numSts[i] - numEns[i]
    num += k
    num -= sumEns[i]
    nums[i%M] += num

print(ans - max(nums))

Solution (Python):
n, m = map(int, input().split())
a = list(map(int, input().split()))

imos = [0] * (2 * m)
diff = [0] * (2 * m)
res = 0
for i in range(n - 1):
    l = a[i] - 1
    r = a[i + 1] - 1
    if l > r:
        r += m
    imos[l + 2] += 1
    imos[r + 1] -= 1
    diff[r + 1] += r - l - 1
    res += r - l

ans = [0] * (2 * m)
tmp = 0
for i in range(2 * m):
    tmp += imos[i]
    if i - 1 >= 0:
        ans[i] += ans[i - 1] + tmp
    else:
        ans[i] += tmp
    ans[i] -= diff[i]
    
max_ = 0
for i in range(m):
    max_ = max(max_, ans[i] + ans[i + m])
print(res - max_)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    n, m = MI()
    
    aa = LI1()
    
    
    pp = [0] * (m + 1)
    qq = [0] * (m + 1)

    for a0, a1 in zip(aa, aa[1:]):
        if a0 < a1:
            pp[a0 + 1] += -1
            pp[a1 + 1] += 1
            qq[0] += a1 - a0
            qq[a0 + 1] += a0 + 1
            qq[a1 + 1] += -a0 - 1
        else:
            pp[0] += -1
            pp[a1 + 1] += 1
            pp[a0 + 1] += -1
            qq[0] += a1 + 1
            qq[a1 + 1] += m - a0 - 1
            qq[a0 + 1] += a0 + 1
    for i in range(1, m):
        pp[i] += pp[i - 1]
        qq[i] += qq[i - 1]
    ans = min(pp[i] * i + qq[i] for i in range(m))
    print(ans)

main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

N,M,*A = map(int,read().split())

def f(x,y,k):
    if x > y:
        y += M
    if k <= x:
        k += M
    if k <= y:
        return (y-k) + 1
    return y-x

add_X = 0
add_DX = 0
DDX = [0] * M
for x,y in zip(A,A[1:]):
    x -= 1
    y -= 1
    a = f(x,y,M-2)
    b = f(x,y,M-1)
    add_X += b
    add_DX += b-a
    d = y - x
    if d < 0:
        d += M
    DDX[(y+1)%M] += d
    DDX[(y+2)%M] -= (d-1)
    DDX[(x+2)%M] -= 1

DX = [add_DX + y for y in itertools.accumulate(DDX)]
X = [add_X + y for y in itertools.accumulate(DX)]

answer = min(X)
print(answer)

Solution (Python):
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
A = list(map(int, input().split()))

start = [0]*M
end = [0]*M
S = [0]*M
a = 0
score = 0
total = 0
for i in range(N-1):
    p, q = A[i]-1, A[i+1]-1
    start[q] += 1
    end[p] += 1
    S[q] += (q-p-1+M)%M
    total += (q-p+M)%M
    score += max(0, (q-p-1+M)%M - q)
    if p > q:
        a += 1

ans = total - score
ind = M-1
for _ in range(4*M):
    a -= end[ind]
    score += S[ind] - a
    a += start[ind]
    ind -= 1
    if ind < -M: ind += M
    ans = min(ans, total-score)
print(ans)

Solution (Python):
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7



N, M = list(map(int, sys.stdin.buffer.readline().split()))
A = list(map(int, sys.stdin.buffer.readline().split()))

counts = [0] * (M + 1)
for a, b in zip(A, A[1:]):
    counts[b] += (b - a) % M
A = np.array(A, dtype=int)
diffs = np.diff(A)
S = (diffs % M).sum()

reduce = (M - A[:-1][diffs < 0]).sum()
d = (diffs < 0).sum()
ans = S
for x in range(1, M + 1):
    ans = min(ans, S - reduce)
    reduce += d - counts[x]
    if A[0] == x:
        d += 1
    if A[-1] == x:
        d -= 1
print(ans)

Solution (Python):
class Binary_Indexed_Tree():
    def __init__(self, n):
        self.bit = [0]*n
        self.n = n
    def add(self, ind, num):
        while(ind <= self.n):
            self.bit[ind - 1] += num
            ind += ind & -ind
    def sum(self, ind):
        ret = 0
        while(ind > 0):
            ret += self.bit[ind-1]
            ind -= ind & -ind
        return ret

class Binary_Indexed_Tree_RAQ_RSQ():
    def __init__(self,n):
        self.p = Binary_Indexed_Tree(n+1)
        self.q = Binary_Indexed_Tree(n+1)

    def add(self, s,t,x):
        t += 1
        self.p.add(s,-x*s)
        self.p.add(t, x*t)
        self.q.add(s,x)
        self.q.add(t,-x)

    def sum(self, s, t):
        t += 1
        return self.p.sum(t) + self.q.sum(t)*t - self.p.sum(s) - self.q.sum(s)*s

n,m = map(int, input().split())
a = list(map(lambda x: int(x)-1, input().split()))
score = Binary_Indexed_Tree_RAQ_RSQ(2*m+10)


for i in range(n-1):
    cur, nxt = a[i], a[i+1]
    if cur > nxt:
        nxt += m
    if cur + 2 <= nxt:
        score.add(cur+3, nxt+1, 1)
        k = nxt-cur-1
        score.add(nxt+2, nxt+2, -k)

scores = [score.sum(0, i+1)+score.sum(0, i+m+1) for i in range(m)]

x = tmp = 0
for i in range(m):
    if scores[i] > tmp:
        x = i
        tmp = scores[i]
ans = 0

def cnt(cur, nxt):
    if cur > nxt:
        nxt += m
    return nxt-cur

for i in range(n-1):
    cur, nxt = a[i], a[i+1]
    ans += min(cnt(cur, nxt), cnt(x, nxt)+1)

print(ans)

Solution (Python):
n, m = map(int, input().split())
A = list(map(lambda x:int(x)-1, input().split()))
value = [0]*(m+1)
length = [0]*(m+1)
ans = 0
for i in range(1, n):
    a, b = A[i-1], A[i]
    if a<b:
        value[a+1]+=1
        value[b+1]-=1
        length[b+1]-=(b-a)
        ans+=b-a
    else:
        value[a+1]+=1
        value[m]-=1
        value[0]+=1
        value[b+1]-=1
        length[0]+=(m-a-1)
        length[b+1]-=(m-a)+(b)
        ans+=m-a+b
for i in range(m):
    value[i+1] = value[i]+value[i+1]
for i in range(m+1):
    length[i] += value[i]
for i in range(m):
    length[i+1] += length[i]
for i in range(m):
    length[i]-=value[i]
ans -= max(length[::-1])
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
from collections import Counter

n, m = [int(item) for item in input().split()]
a = [int(item) - 1 for item in input().split()]
cnt_t = [0] * m

ans = [0] * m
cnt_r = [0] * (m + 1)
for a1, a2 in zip(a, a[1:]):
    ans[0] += min((m + a2 - a1) % m, (m + a2 - 0) % m + 1)
    cnt_t[a2] += (m + a2 - a1) % m - 1
    if (m + a2 - a1) % m <= 1:
        continue
    add = (a1 + 2) % m
    sub = a2 + 1
    if add < sub:
        cnt_r[add] += 1
        cnt_r[sub] -= 1
    else:
        cnt_r[add] += 1
        cnt_r[sub] -= 1
        cnt_r[0] += 1
        cnt_r[m] -=1
for i in range(m):
    cnt_r[i+1] += cnt_r[i]

for i in range(1, m):
    ans[i] = ans[i - 1] - cnt_r[i] + cnt_t[i - 1]
print(min(ans))

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    N,M = map(int,input().split())
    A = list(map(int,input().split()))
    S = [0]*(2*M+3)
    for i in range(N-1):
        now = A[i]
        nex = A[i+1]
        L = nex-now
        if L-1>0:
            S[now+2] += 1
            S[nex+1] += -L
            S[nex+2] += L-1
        elif L<0:
            L = L%M
            if L-1>0:
                S[now+2] += 1
                S[nex+1+M] += -L
                S[nex+2+M] += L-1
        
    
    for i in range(2*M+2):
        S[i+1] += S[i]
    
    for i in range(2*M+2):
        S[i+1] += S[i]
    
    B = [0]*(M+1)
    for i in range(1,M+1):
        B[i] = S[i] + S[i+M]
    X = 1
    diff = 0
    for i in range(1,M+1):
        if B[i] > diff:
            diff = B[i]
            X = i
    SS = 0
    for i in range(N-1):
        SS += (A[i+1]-A[i])%M
    
    print(SS-diff)        
            
    
    
main()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res

def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    n = I()

    return


def B():
    n = I()

    return


def C():
    n,m = LI()
    a = LI()
    for i in range(n):
        a[i] -= 1
    b = [0]*(m+10)
    ans = 0
    f = [0]*(m+10)
    for i in range(n-1):
        r = (a[i+1]-a[i])%m
        ans += r
        if r < 2:
            continue
        if a[i+1] >= (a[i]+2)%m:
            f[(a[i]+2)%m] += 1
            b[(a[i]+2)%m] += 1
            b[a[i+1]+1] -= 1
            f[a[i+1]+1] -= r
        else:
            b[0] += 1
            f[0] += (-a[i]-1)%m
            b[a[i+1]+1] -= 1
            f[a[i+1]+1] -= r
            b[a[i]+2] += 1
            f[a[i]+2] += 1
            b[m] -= 1
    for i in range(m-1):
        b[i+1] += b[i]
    for i in range(m-1):
        f[i+1] += f[i]+b[i]
    print(ans-max(f))
    return


def D():
    n = I()

    return


def E():
    n = I()

    return


def F():
    n = I()

    return


if __name__ == "__main__":
    C()

Solution (Python):
N, M = map(int, input().split())
a = list(map(lambda x: int(x) - 1, input().split()))
P = 300005
d1 = [0] * P
d2 = [0] * P
s = 0
for i in range(N - 1):
    x = a[i]
    y = a[i + 1]
    if y < x:
        y += M
    s += y - x
    if x + 1 < y:
        d1[x + 2] += 1
        d1[y + 1] -= 1
        d2[y + 1] += y - x - 1
        d1[M + x + 2] += 1
        d1[M + y + 1] -= 1
        d2[M + y + 1] += y - x - 1

ans = float('inf')
for i in range(3 * M):
    if i > 0:
        d1[i] += d1[i - 1]
        d2[i] += d2[i - 1]
    d2[i] -= d1[i]
    ans = min(ans, s + d2[i])

print(ans)

Solution (Python):
from collections import defaultdict


n, m = map(int, input().split())
light_list = list(map(int, input().split()))
ret = 0

diff_dict = defaultdict(int)
cnt=0
for i in range(n-1):
    if light_list[i+1] > light_list[i]:
        diff_dict[light_list[i+1]+1] += light_list[i+1] - light_list[i]
        ret += light_list[i+1] - light_list[i]
    else:
        diff_dict[light_list[i+1]+1] += m - (light_list[i] - light_list[i+1])
        ret += light_list[i+1]
        cnt += 1


ret_min = float('inf')
for i in range(1, m+1):
    if i-1 == light_list[0]:
        cnt += 1
    if i-1 == light_list[-1]:
        cnt -= 1
    if diff_dict[i]:
        ret += diff_dict[i]
    ret -= cnt
    ret_min = min(ret+cnt, ret_min)




print(ret_min)