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-----
4 6
1 5 1 4

-----Sample Output-----
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.

Difficulty: competition

Starter code:

Solutions:
n,m=map(int,input().split())
A=[int(i)-1 for i in input().split()]
ds=[0]*m
de=[[] for i in range(m)]
h,dec=0,0
for i in range(n-1):
  if A[i+1]-A[i]>0:
    h+=A[i+1]-A[i]
  else:
    h+=A[i+1]+1
    dec+=1
  de[A[i+1]].append((i,(A[i+1]-A[i])%m))
for i in range(m):
  for a in de[i]:
    ds[(i-a[1]+1)%m]+=1
ans=float("inf")
for i in range(m):
  for a in de[i]:
    h+=a[1]-1
    dec-=1
  h-=dec
  ans=min(h,ans)
  if i<=m-2:
    dec+=ds[i+1]
  
print(ans)

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
s = [0] * (2 * m + 1)
cnt = [0] * (m + 1)
for i in range(n - 1):
    cnt[a[i + 1]] += (a[i + 1] + m - a[i]) % m - 1
for i in range(n - 1):
    s[a[i] + 1] += 1
    if a[i + 1] < a[i]:
        s[a[i + 1] + m] -= 1
    else:
        s[a[i + 1]] -= 1

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

tmp = 0
for i in range(n - 1):
    if a[i + 1] < a[i]:
        tmp += (a[i + 1] - 1) + 1
    else:
        tmp += (a[i + 1] - a[i])
ans = tmp
for i in range(2, m + 1):
    tmp = tmp + cnt[i - 1] - s[i - 1]
    ans = min(ans, tmp)
print(ans)


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


A = [int(s) for s in input().split()]

A = [(a-A[0])%m for a in A]

end = A[-1]

dist = [0]*m
cycles = 0
x = 0

for a,b in zip(A[:-1],A[1:]):
  cycles += b < a
  dist[b] += (b-a)%m
  x += min((b-a)%m, 1 + b)

dist[0] += 1

res = x

for k in range(m):

  x += dist[k]
  x -= cycles + (k <= end)

  res = min(res, x)

print(res)

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

imos = [0] * (2*M+1)
ends = [0] * (2*M+1)
max_press = 0
for a,b in zip(src,src[1:]):
    if a > b:
        b += M
    if b-a > 1:
        imos[a+2] += 1
        imos[b+1] -= 1
        ends[b+1] += b-a-1
    max_press += b-a

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

press = [max_press] * M
d = 0
for i,(dec,inc) in enumerate(zip(imos, ends)):
    d += inc - dec
    press[i%M] += d
print(min(press))

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def M(n): return ModInt(n)
def MI(): return M(I())

class ModInt():
    def __init__(self, n):
        self.n = n

    def __add__(self, x):
        x = ModInt.xn(x)
        return ModInt((self.n+x) % mod)

    def __sub__(self, x):
        x = ModInt.xn(x)
        return ModInt((self.n-x) % mod)

    def __mul__(self, x):
        x = ModInt.xn(x)
        return ModInt((self.n*x) % mod)

    def __truediv__(self, x):
        x = ModInt.xn(x)
        return ModInt(self.n * pow(x, mod-2, mod) % mod)

    @classmethod
    def xn(cls, x):
        if isinstance(x, ModInt):
            return x.n
        return x

    def __str__(self):
        return str(self.n)

def main():
    n,m = LI()
    a = LI_()
    b = [0] * (m*2)
    c = [[] for _ in range(m*2)]
    r = 0
    for i in range(1,n):
        d = a[i-1]
        e = a[i]
        if e < d:
            e += m
        b[d+2] += 1
        c[e].append(e-d-1)
        r += e-d

    f = [0] * (m*2)
    t = 0
    tt = 0
    for i in range(1,m*2):
        t += b[i]
        tt += t
        f[i] += tt
        for g in c[i]:
            t -= 1
            tt -= g
    for i in range(m):
        f[i] += f[i+m]

    return r - max(f)

print((main()))





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()
    # 明るさaは0-indexedにする
    aa = LI1()
    # 頂点xをお気に入りにしたときのスコアをpx+qで表す
    # imos法を使う
    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()



"""
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

#print (start,end)

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

    #print (i+1,imosnum,plus)

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

n,m,*A=list(map(int,open(0).read().split()))
D=[0]*(2*m+2)
cur = 0
S = 0
for a,b in zip(A,A[1:]):
    S += (b-a)%m
    b += m*(b<a)
    k = b-a
    if k>1:
        D[a+2] += 1
        D[b+1] -= k
        D[b+2] += k-1
for i in range(1,2*m+2):
    D[i]+=D[i-1]
for i in range(1,2*m+2):
    D[i]+=D[i-1]
print((S-max(D[a]+D[a+m]for a in A)))


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

def solve(n, m, As):
    weighted_sum = [0] * m
    row_sum = [0] * m
    col_sum = [0] * m
    delta_sum = [0] * m
    delta_sum0 = 0
    delta_weighted = 0
    sol = 0
    As = [a - 1 for a in As]
    for i in range(n - 1):
        a = As[i]
        b = As[i + 1]
        sol += (b - a) % m
        if a == b or (a + 1)%m == b: continue
        row_sum[a] += 1
        col_sum[b] += 1
        weighted_sum[b] += (b - a - 1) % m
        if (a > b and a != m - 1):
            delta_sum0 += 1
            delta_weighted += m - a - 1
    delta_sum[0] = delta_sum0
    for i in range(1, m):
        delta_sum0 = delta_sum0 + row_sum[i - 2] - col_sum[i - 1]
        delta_sum[i] = delta_sum0
    record = delta_weighted
    for x in range(1, m):
        delta_weighted += delta_sum[x] - weighted_sum[x - 1]
        record = max(record, delta_weighted)
    return sol - record
    
print((solve(n, m, As)))


"""
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

# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,m,*a = list(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(w)

#print(ans)
print((ans+v))    









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

# print(imos)

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

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

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

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

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()

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))

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
bitween = [0 for i in range(2 * m + 10)]
edge = [[] for i in range(m + 1)]

ans = 0
for i in range(n - 1):
	l, r = a[i], a[i + 1]
	if l >= r:
		r += m
	bitween[l + 2] += 1
	bitween[r + 1] -= 1

	edge[a[i + 1]].append(i)

for i in range(2 * m + 1):
	bitween[i + 1] += bitween[i]

ans = 0
for i in range(n - 1): # x = 1
	ans += min((a[i + 1] - a[i] + m) % m, (a[i + 1] - 1 + m) % m + 1)
prv = ans
for i in range(2, m + 1): # x >= 2
	crt = prv - bitween[i] - bitween[i + m]
	for j in edge[i - 1]:
		crt -= min((a[j + 1] - a[j] + m) % m, (a[j + 1] - (i - 1) + m) % m + 1)
		crt += min((a[j + 1] - a[j] + m) % m, (a[j + 1] - i + m) % m + 1 )
	ans = min(ans, crt)
	prv = crt
print(ans)


# Binary Indexed Tree (Fenwick Tree)
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))

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    N, M = list(map(int, readline().split()))
    A = list([int(x) - 1 for x in readline().split()])

    b = [0] * M

    for i in range(N - 1):
        prev = A[i]
        cur = A[i + 1]
        if prev < cur:
            b[prev + 1] += 1
            b[cur] -= 1
        else:
            if (prev+1) % M > 0:
                b[(prev + 1) % M] += 1
            b[0] += 1
            b[cur] -= 1

    acc = [0] * M

    for i in range(M):
        if i > 0:
            acc[i] = acc[i - 1] + b[i]
        else:
            acc[i] = b[i]

    score = 0

    cnt = [0] * M

    for i in range(N - 1):
        prev = A[i]
        cur = A[i + 1]
        cnt[cur] += (cur + M - prev - 1) % M

    for i in range(N - 1):
        prev = A[i]
        cur = A[i + 1]
        first = (cur + M - prev) % M
        second = (cur + M) % M + 1
        score += min(first, second)
    ans = score

    for i in range(1, M):
        score += cnt[i - 1]
        score -= acc[i - 1]
        ans = min(ans, score)

    print(ans)


def __starting_point():
    main()

__starting_point()

from collections import Counter, defaultdict

n, m = [int(c) for c in input().split()]
xs = [int(c) for c in input().split()]


def ring_cost(fr, to):
    return to - fr if to >= fr else (m - fr) + to

from_counter = Counter(xs[:-1])
to_counter = Counter(xs[1:])

fav = 1
cost = 0
use_fav = 0
nofav_cost = defaultdict(int)

for i in range(n - 1):
    normal_cost = ring_cost(xs[i], xs[i+1])
    fav_cost = ring_cost(fav, xs[i+1]) + 1
    cost += min(normal_cost, fav_cost)
    nofav_cost[xs[i+1]] += normal_cost
    if fav_cost <= normal_cost:
        use_fav += 1

ans = cost
for fav in range(2, m+1):
    stop_using_fav = to_counter[fav - 1]
    use_fav -= stop_using_fav
    cost += nofav_cost[fav - 1] - stop_using_fav

    cost -= use_fav

    use_fav += from_counter[fav - 1]
    ans = min(ans, cost)
    # print(fav, cost)

print(ans)

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]))

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

D0 = [0]*(2*m+10)
D1 = [0]*(2*m+10)
ans = 0

pa = A[0]-1
for a in A[1:]:
    a -= 1
    if a<pa:
        a += m
    ans += a-pa
    D1[pa+1] += 1
    D1[a] -= a-pa
    D1[a+1] += a-pa-1
    pa = a%m

for i, d1 in enumerate(D1):
    D0[i] = d1 + D0[i-1]

L = [0]*(2*m+10)

for i, d0 in enumerate(D0):
    L[i] = d0 + L[i-1]

for i, l in enumerate(L[m:]):
    L[i%m] += l

print((ans-max(L[:m])))


mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    N, M = list(map(int, input().split()))
    A = list(map(int, input().split()))
    A = [a - 1 for a in A]
    imos = [0] * M
    imos_2 = [0] * M
    B = [0] * M
    base = 0
    for i in range(1, N):
        if A[i] > A[i-1]:
            k = A[i] - A[i - 1]
            base += k
            if k == 1:
                continue
            if A[i] + 1 < M:
                imos_2[A[i] + 1] += k
            if A[i] + 2 < M:
                imos_2[A[i] + 2] += -(k-1)
            imos_2[A[i - 1] + 2] += -1
        else:
            k = A[i] - A[i-1] + M
            base += k
            if k == 1:
                continue
            if A[i-1] == M-1:
                imos_2[1] += -1
                imos_2[A[i] + 1] += k
                if A[i] + 2 < M:
                    imos_2[A[i] + 2] += -(k-1)
            else:
                imos_2[(A[i] + 2)%M] += -(k-1)
                imos_2[(A[i] + 1)%M] += k
                imos_2[(A[i - 1] + 2) % M] += -1
                if A[i - 1] + 2 < M:
                    B[0] += -(M - (A[i-1] + 2))
                    imos_2[0] += -1
    for i in range(M):
        if i == 0:
            imos[i] += imos_2[i]
        else:
            imos[i] += imos[i-1] + imos_2[i]
        if i == 0:
            B[i] = B[i] + imos[i]
        else:
            B[i] = B[i-1] + imos[i]
    print((min(B) + base))


def __starting_point():
    main()

__starting_point()

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
  #print(imosb)
#print(d)

imos = [0] * (M + 2)
for i in range(2 * M + 1):
  imosa[i + 1] += imosa[i]
  imosb[i + 1] += imosb[i]
#print(imosa)
#print(imosb)
for i in range(M + 2):
  imos[i] = imosa[i] * i + imosa[i + M] * (i + M) + imosb[i] + imosb[i + M]
#print(imos)
print(sum(d) - max(imos[1: M + 1]))

n, m = list(map(int, input().split()))
a = [int(x) for x in input().split()]
ps = [0]*(m+2)  # 0,1,2,...,m,m+1

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)))


#!usr/bin/env python3
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

#A
def A():
    n = I()

    return

#B
def B():
    n = I()

    return

#C
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

#D
def D():
    n = I()

    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

#Solve
def __starting_point():
    C()

__starting_point()

_,m,*A=map(int,open(0).read().split());S=l=3*m;D=[0]*l
for a,b in zip(A,A[1:]):b+=m*(b<a);k=b-a;S+=k;D[a+2]+=1;D[b+1]-=k;D[b+2]+=k-1
for i in range(l*2):D[i%l]+=D[~-i%l]
print(S-l-max(D[a]+D[a+m]for a in A))

from collections import defaultdict
from itertools import accumulate

n, m = list(map(int, input().split()))
aa = list(map(int, input().split()))
counter = defaultdict(list)

cum = [0] * (m + 2)
ans_1 = 0
for a, b in zip(aa, aa[1:]):
    counter[b].append(a)
    cum[a + 1] += 1
    cum[b] += -1
    if a > b:
        cum[1] += 1
        ans_1 += b
    else:
        ans_1 += b - a

cum = list(accumulate(cum))

ans_prev = ans_1
ans_min = ans_1
for x in range(2, m + 1):
    ans_x = ans_prev
    px = x - 1
    if px in counter:
        ans_x += sum((px - a) % m - 1 for a in counter[px])
    ans_x -= cum[px]
    ans_min = min(ans_min, ans_x)
    ans_prev = ans_x
print(ans_min)


n, m = list(map(int, input().split()))
A = list(map(int, input().split()))
S = 0
for i in range(n-1):
    S += (m + A[i+1] - A[i]) % m

T = 2*m
D = [0]*(T+10)
data = [0]*(T+1)
def get(i):
    s = 0
    while i:
        s += data[i]
        i -= i & -i
    return s
def add(i, x):
    while i <= T:
        data[i] += x
        i += i & -i

for i in range(n-1):
    x = A[i]; y = A[i+1]
    if y < x:
        y += m
    k = y-x
    if k > 1:
        D[x+2] += 1
        D[y+1] -= k
        D[y+2] += k-1
for i in range(1, 2*m+5):
    D[i] += D[i-1]
    add(i, D[i])
res = min(S - (get(a) + get(a+m)) for a in A)
print(res)


import sys
def MI(): return list(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)
# (X[0]+…+X[i])*i+(Y[0]+…+Y[i]) = お気に入りボタンをiに設定した時に、ボタンの押す回数を何回節約できるか

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)))


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))

_,m,*A=map(int,open(0).read().split());S=l=3*m;D=[0]*l
for a,b in zip(A,A[1:]):b+=m*(b<a);k=b-a;S+=k;D[a+2]+=1;D[b+1]-=k;D[b+2]+=k-1
exec("for i in range(l):D[i]+=D[i-1]\n"*2);print(S-l-max(D[a]+D[a+m]for a in A))

import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return list(map(int, input().split()))
def LI(): return list(map(int, input().split()))
mod=10**9+7


"""
xを決めればO(N)で答えが求まる.
全部は求められない.
xを変更したときの差分に注目.


aからbへ
順送りだけのとき,(b-a)%M
お気に入りを使うとき,1 + (b-x)%M

目標地点がxだった場合，お気に入りを+1すると一気に(b-a)%M-1回必要になる
元々お気に入りを使うケース(a<x<bみたいな)では-1
それ以外なら変化なし

目標地点の値は普通に数える
お気に入りを使うケースはimosで.区間(a,b)に+1する感じ.
a>bの場合,(0,b)と(a,N]に+1かな
"""

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

S=[0]*(M+3)

prev=[[]for _ in range(M+1)]
for i in range(N-1):
    # 直前の数字
    b=A[i+1]
    a=A[i]
    prev[b].append(a)
    
    # imos
    if b>a:
        S[a+1]+=1
        S[b]-=1
    elif a>b:
        S[1]+=1
        S[b]-=1
        S[a+1]+=1
        S[-1]-=1
        
for i in range(M-1):
    S[i+1]+=S[i]

ans=0
x=1
now=A[0]
for i in range(1,N):
    nxt=A[i]
    if nxt>now:
        ans+=nxt-now
    else:
        ans+=nxt
    now=nxt

# print(1,ans)
temp=ans
for x in range(1,max(A)):
    for p in prev[x]:
        temp+=(x-p)%M - 1
    temp-=S[x]
    # print(x+1,temp)
    ans=min(ans,temp)
    
print(ans)

# print(S)
# print(prev)




from itertools import accumulate
import sys
input = sys.stdin.readline

n, m = list(map(int, input().split()))
a = list([int(x) - 1 for x in 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)



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 = list(map(int, input().split()))
a = list([int(x) - 1 for x in 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)


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))

from itertools import accumulate
import sys
input = sys.stdin.readline

n, m = list(map(int, input().split()))
a = list([int(x) - 1 for x in 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)



import sys
input = sys.stdin.readline
import itertools

"""
(a_i+1,a_{i+1}] に x がある間は...使う。傾き-1
a_{i+1} -> a_{i+1} + 1 のところでがくっと下がる
そこからa_iまでは傾き0
""" 

N,M = map(int,input().split())
A = [int(x) for x in input().split()]
FROM = A[:-1]
TO = A[1:]

d_slope = [0] * (M+1) # 傾きの差分

"""
5,4,3,2,1,5,5,5,5
0,-1,-1,-1,-1,4,0,0,0
0,-1,0,0,0,0,5,-4,0,0
"""

for x,y in zip(FROM,TO):
    if y < x:
        y += M
    z = y - x
    if z == 1:
        continue
    d_slope[1+(x+1)%M] += -1
    d_slope[1+y%M] += z # 1回で行けたのがz回かかるようになる
    d_slope[1+(y+1)%M] += 1-z

slope = list(itertools.accumulate(d_slope))
S = sum(slope)
slope = [x - S//M for x in slope]
slope[0] = 0

# 1番をお気に入りにしたときのスコアを求める
cnt = 0
for x,y in zip(FROM,TO):
    if x < y:
        cnt += (y-x)
    else:
        cnt += y

answer = cnt - slope[1] + min(itertools.accumulate(slope[1:]))
print(answer)


def main(n,m,a):
    mat=[0]*m
    dat=[set() for _ in range(m)]
    ret=[0]*m
    base=0
    for i in range(n-1):
        base+=(a[i+1]-a[i])%m
        if (a[i+1]-a[i])%m<2:continue
        mat[a[i+1]-1]+=(a[i+1]-a[i])%m-1
        dat[a[i+1]-1].add(i+1)
        dat[(a[i])%m].add(-i-1)
    now=0
    nowd=set()
    for i in range(m-1,-1,-1):
        now+=mat[i]
        mat[i]=0
        ret[i]+=now
        delid=set()
        for x in dat[i]:
            if x>0:
                nowd.add(x)
                delid.add(x)
            elif -x in nowd:
                nowd.discard(-x)
                delid.add(x)
        for x in delid:
            dat[i].discard(x)
        now=max(now-len(nowd),0)
    for i in range(m-1,-1,-1):
        now+=mat[i]
        mat[i]=0
        ret[i]+=now
        delid=set()
        for x in dat[i]:
            if x>0:
                nowd.add(x)
                delid.add(x)
            elif -x in nowd:
                nowd.discard(-x)
                delid.add(x)
        for x in delid:
            dat[i].discard(x)
        now=max(now-len(nowd),0)
    
    return base-max(ret)
n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
print((main(n,m,a)))


#!/usr/bin/env python3


def solve(n, m, a):

    ans = 0
    s = [(a[0], 0)]
    for i in range(1, n):
        ans += (a[i] - a[i - 1]) % m
        s.append((a[i], i))
    s.sort()


    r = [0] * (m + 1)
    c = 0
    t = 0
    active = [0] * n
    j = 0
    while j < n:
        aj, _ = s[j]
        r[aj] += (aj * c - t - c)
        while j < n:
            ai, i = s[j]
            if ai != aj:
                break
            if 0 < i:
                if active[i - 1]:
                    active[i - 1] = 0
                    c -= 1
                    t -= a[i - 1]
            if i < n - 1:
                active[i] = 1
                c += 1
                t += a[i]
            j += 1

    if 0 < c:
        t -= m * c
        j = 0
        while j < n:
            aj, _ = s[j]
            r[aj] += (aj * c - t - c)
            while j < n:
                ai, i = s[j]
                if ai != aj:
                    break
                if 0 < i:
                    if active[i - 1]:
                        active[i - 1] = 0
                        c -= 1
                        t -= a[i - 1] - m
                j += 1
            if c == 0:
                break

    ans -= max(r)

    return ans


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

    print((solve(n, m, a)))


def __starting_point():
    main()


__starting_point()

from collections import defaultdict
from itertools import accumulate

n, m = list(map(int, input().split()))
aa = list(map(int, input().split()))
counter = defaultdict(list)

cum = [0] * (m + 2)
ans_1 = 0
for a, b in zip(aa, aa[1:]):
    counter[b].append(a)
    cum[a + 1] += 1
    cum[b] += -1
    if a > b:
        cum[1] += 1
        ans_1 += b
    else:
        ans_1 += b - a

cum = list(accumulate(cum))

ans_prev = ans_1
ans_min = ans_1
for x in range(1, m):
    ans_x = ans_prev
    if x in counter:
        ans_x += sum((x - a) % m - 1 for a in counter[x])
    ans_x -= cum[x]
    ans_min = min(ans_min, ans_x)
    ans_prev = ans_x
print(ans_min)


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

a0 = a[0]

DDF = [0 for _ in range(m)] #DF[i] = F[i] - F[i-1], DDF[i] = DF[i] - DF[i-1] (DF[0] = DDF[0] = 0とおく)
A = [m-1]
for i in range(1,n):
  A.append((a[i]-a0-1) % m)
#print("A : ", A)
total_step = 0
for i in range(1,n):
  total_step += (a[i]-a[i-1]) % m

for i in range(1,n):
  # if A[i] > A[i-1]: DF[A[i-1]+2 : A[i]+1] += 1
  # if A[i] < A[i-1]: DF[A[i-1]+2 : m] += 1; DF[1:A[i]+1] += 1; DF[0] += m-A[i-1]-1
  # DF[A[i]+1] -= (A[i] - A[i-1]) % m - 1
  if A[i] > A[i-1]:
    if A[i-1] < m-2: DDF[A[i-1]+2] += 1
    if A[i] < m-1: 
      DDF[A[i]+1] -= 1 + (A[i] - A[i-1]) % m - 1
      if A[i] < m-2:
        DDF[A[i]+2] += (A[i] - A[i-1]) % m - 1
  elif A[i] < A[i-1]:
    if A[i-1] < m-2: 
      DDF[A[i-1]+2] += 1
    DDF[0] += m-A[i-1]-1
    DDF[1] -= (m-A[i-1]-1) - 1
    if A[i] < m-1: 
      DDF[A[i]+1] -= 1 + (A[i] - A[i-1]) % m - 1
      if A[i] < m-2:
        DDF[A[i]+2] += (A[i] - A[i-1]) % m - 1
  """
  print("DDF @ ", i," : ", DDF) 
  DF = [0 for _ in range(m)]
  DF[0] = DDF[0]
  for i in range(1,m):  
    DF[i] = DF[i-1] + DDF[i]
  print("DF : ", DF)  
  F = [0 for _ in range(m)]
  F[0] = DF[0]
  for i in range(1,m):  
    F[i] = F[i-1] + DF[i]
  print("F : ", F)    
  """
  
for i in range(1,m):  
  DDF[i] = DDF[i-1] + DDF[i]
#print("DF : ", DDF)    
for i in range(1,m):  
  DDF[i] = DDF[i-1] + DDF[i]
#print("F : ", DDF)    
print(total_step - max(DDF))

n,m,*A=map(int,open(0).read().split());l=3*m;D=[0]*l;S=0
for a,b in zip(A,A[1:]):
 b+=m*(b<a);k=b-a;S+=k
 if k>1:D[a+2]+=1;D[b+1]-=k;D[b+2]+=k-1
exec("for i in range(1,l):D[i]+=D[i-1]\n"*2);print(S-max(D[a]+D[a+m]for a in A))

# E
n, m = map(int, input().split())
a_list = list(map(int, input().split()))


# bonus map
bonus_str_cnt = [0]*(m+1)
bonus_end_vol = [0]*(m+1)
bonus_end_cnt = [0]*(m+1)

# 1
one_res = 0
bonus_cnt = 0
for i in range(n-1):
    difm = (a_list[i+1] - a_list[i]) % m
    if difm > 1:
        if a_list[i] + 2 > m:
            bonus_str_cnt[(a_list[i] + 2) - m] += 1
        else:
            bonus_str_cnt[a_list[i] + 2] += 1
        bonus_end_cnt[a_list[i+1]] += 1
        bonus_end_vol[a_list[i+1]] += difm - 1
    if difm <= a_list[i+1]:
        one_res += difm
    else:
        one_res += a_list[i+1]
        bonus_cnt += 1

res_list = [one_res]
res = one_res
for i in range(2, m+1):
    res += bonus_end_vol[i-1]
    bonus_cnt += bonus_str_cnt[i] - bonus_end_cnt[i-1]
    res -= bonus_cnt
    res_list.append(res)

print(min(res_list))

N, M = list(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)))


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
        #print(S)
    #print(S)
    for i in range(2*M+2):
        S[i+1] += S[i]
    #print(S)
    for i in range(2*M+2):
        S[i+1] += S[i]
    #print(S)
    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(B)
    print(SS-diff)        
            
    
    
main()

n, m = list(map(int, input().split()))
A = list(map(int, input().split()))
S = 0
for i in range(n-1):
    S += (m + A[i+1] - A[i]) % m

T = 2*m
D = [0]*(T+10)
data = [0]*(T+1)
def get(i):
    s = 0
    while i:
        s += data[i]
        i -= i & -i
    return s
def add(i, x):
    while i <= T:
        data[i] += x
        i += i & -i

for i in range(n-1):
    x = A[i]; y = A[i+1]
    if y < x:
        y += m
    k = y-x
    if k > 1:
        D[x+2] += 1
        D[y+1] -= k
        D[y+2] += k-1
for i in range(1, 2*m+5):
    D[i] += D[i-1]
    add(i, D[i])
res = min(S - (get(a) + get(a+m)) for a in A)
print(res)


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))

n, m = map(int, input().split())
a = list(map(int, input().split()))
a = [b-1 for b in a]
imos = [0 for _ in range(m+1)]
base = 0
for i in range(n-1):
	x, y = a[i], a[i+1]
	if y-x == 1 or x+1-m == y:
		continue
	z, w = (x+2)%m, (y+1)%m
	if w == 0:
		w = m
	if z < w:
		imos[z] += 1
		imos[w] -= w-z+1
		if w < m:
			imos[w+1] += w-z
	else:
		imos[z] += 1
		imos[m] -= m-z+1
		imos[0] += 1
		base += m-z
		imos[w] -= m+w-z+1
		if w < m:
			imos[w+1] += m+w-z
#print(imos)
#print(base)
for i in range(m):
	imos[i+1] += imos[i]
imos[0] += base
for i in range(m):
	imos[i+1] += imos[i]
res = max(imos[:m])
ans = 0
for i in range(n-1):
	if a[i+1] > a[i]:
		ans += a[i+1] - a[i]
	else:
		ans += a[i+1] + m - a[i]
#print(ans)
ans -= res
print(ans)

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)

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_)

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)

from collections import defaultdict


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

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

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


n, m = list(map(int, input().split()))
aa = list(map(int, input().split()))
counter = defaultdict(list)

bit = Bit(m + 1)
ans_1 = 0
for a, b in zip(aa, aa[1:]):
    counter[b].append(a)
    bit.add(a + 1, 1)
    bit.add(b, -1)
    if a > b:
        bit.add(1, 1)
        ans_1 += b
    else:
        ans_1 += b - a

ans_prev = ans_1
ans_min = ans_1
for x in range(2, m + 1):
    ans_x = ans_prev
    px = x - 1
    if px in counter:
        ans_x += sum((px - a) % m - 1 for a in counter[px])
    ans_x -= bit.sum(px)
    ans_min = min(ans_min, ans_x)
    ans_prev = ans_x
print(ans_min)


from itertools import accumulate
def inpl(): return list(map(int, input().split()))

N, M = inpl()
A = [a-1 for a in inpl()]
S = [0]*(M+1)
T = [0]*(M+1)

tmp = 0
for i in range(N-1):
    T[A[i+1]] += (A[i+1] + M - A[i])%M - 1
    if A[i] < A[i+1]:
        S[A[i]+1] += 1
        S[A[i+1]] -= 1
        tmp += A[i+1] - A[i]
    else:
        tmp += A[i+1] + 1
        S[0] += 1
        S[A[i+1]] -= 1
        S[A[i]+1] += 1

S = list(accumulate(S))
ans = tmp*1
for i in range(1, M):
    tmp2 = tmp + T[i-1] - S[i-1]
    ans = min(ans, tmp2)
    tmp = tmp2
print(ans)

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)

_,m,*A=map(int,open(0).read().split());S=l=3*m;D=[0]*l
for a,b in zip(A,A[1:]):
 b+=m*(b<a);k=b-a;S+=k
 if k>1:D[a+2]+=1;D[b+1]-=k;D[b+2]+=k-1
exec("for i in range(l):D[i]+=D[i-1]\n"*2);print(S-l-max(D[a]+D[a+m]for a in A))

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)

import sys
input = sys.stdin.readline
n, m = map(int,input().split())
A = list(map(int,input().split()))
for i in range(n):
    A[i] -= 1

class Bit:  # Fenwick Tree と同じ
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
  
    def sum(self, l, r):  # [l,r)の和を求める
        # 内部的には[l+1,r+1)の和つまり(rまでの和-lまでの和)
        s = 0
        while r > 0:
            s += self.tree[r]
            r -= r & -r  # 2進数の最も下位の1を取り除くという意味(例:1010→1000)
        while l > 0:
            s -= self.tree[l]
            l -= l & -l  # 2進数の最も下位の1を取り除くという意味(例:1010→1000)
        return s
  
    def add(self, i, x):  # i番目にxを足す
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i  # 2進数の最も下位の1を繰り上げるという意味(例:1010→1100)

    def sett(self, i, x):  # i番目をxにする
        self.add(i, x - self.sum(i, i+1))

    def print_bit(self): # 内部状態をindex順に出力
        print([self.sum(i, i+1) for i in range(self.size)])

    def print_sum(self): # 累積和をindex順に出力
        print([self.sum(0, i+1) for i in range(self.size)])

    def lower_bound_left(self, w):  # xまでの和がw以上となる最小のx、総和がw未満の場合nが返る
        n = self.size
        r = 1
        x = 0
        if self.sum(0, n) < w:
            return n
        while r < n:
            r *= 2
        le = r
        while le > 0:
            if (x + le < n and self.tree[x+le] < w):
                w -= self.tree[x+le]
                x += le
            le //= 2
        return x

    def upper_bound_left(self, w):  # xまでの和がwより大きくなる最小のx、総和がw以下の場合nが返る
        n = self.size
        r = 1
        x = 0
        if self.sum(0, n) <= w:
            return n
        while r < n:
            r *= 2
        le = r
        while le > 0:
            if (x + le < n and self.tree[x+le] <= w):
                w -= self.tree[x+le]
                x += le
            le //= 2
        return x

    def lower_bound_right(self, w):  # xまでの和がw以下となる最大のx、0番目がwより大きい場合-1が返る
        return self.upper_bound_left(w) - 1

    def upper_bound_right(self, w):  # xまでの和がw未満となる最大のx、0番目がw以上の場合-1が返る
        return self.lower_bound_left(w) - 1

B = Bit(m*3)

for i in range(n-1):
    a = A[i]
    b = A[i+1]
    if a == b:
        continue
    d = (b-a) % m
    ra = d - 1
    l1 = a + 2
    r1 = l1 + ra
    B.add(l1, 1)
    B.add(r1, -1)
    B.add(r1, -ra)
    B.add(r1+1, ra)
    # lm1 = r1
    # rm1 = min(r1 + ra, a + m + 1)
    # B.add(lm1, -1)
    # B.add(rm1, 1)
    # p = (r1-l1) - (rm1-lm1)
    # print("p",p)
    # if p > 0:
    #     B.add(rm1-1, -p)
    #     B.add(rm1, p)
    # B.print_sum()

S = [B.sum(0, i+1) for i in range(3*m)]
for i in range(1, 3*m):
    S[i] += S[i-1]

# print(S)

ANS = [0] * m
for i in range(3*m):
    ANS[i%m] += S[i]

now = 0
for i in range(n-1):
    now += (A[i+1]-A[i]) % m

print(now - max(ANS))    

N, M = list(map(int, input().split()))        # N = 配列サイズ
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)))




from itertools import accumulate
def acc(X): return list(accumulate(X))

N, M = map(int, input().split())
A = [int(a)-1 for a in input().split()]

X = [0] * M # 1,1,1,...
Y = [0] * M # 1,2,3,...

def tri(l, r, a = 1):
    if l < M:
        Y[l] += a
    if r + 1 < M:
        Y[r+1] -= a
        X[r+1] -= (r-l+1) * a

def box(l, r, a = 1):
    if l < M:
        X[l] += a
    if r + 1< M:
        X[r+1] -= a
    
def calc(a, b):
    if a <= b - 2:
        tri(a+2, b)
    elif a > b and a <= b + M - 2:
        tri(a+2, M-1)
        tri(0, b)
        box(0, b, -a+M-2)
        
    # print(a, b, X, Y, rev())

def rev():
    ret = acc(Y)
    ret = [X[i] + ret[i] for i in range(M)]
    return acc(ret)
    
ans = 0
for i in range(1, N):
    ans += (A[i] - A[i-1]) % M
    calc(A[i-1], A[i])

X = rev()
# print(X)
ans -= max(X)
print(ans)

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)


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()))

import itertools
def inpl(): return [int(i) for i in input().split()]

n, m = inpl()
a = [int(i)-1 for i in input().split()]
tans = [0]*2*m
Mi = []
Si = 0
for a0, a1 in zip(a, a[1:]):
    if a1 < a0:
        a1 += m
    tans[a0+2] += 1
    tans[a1+1] -= 1
    Mi.append((a1+1, 1+a0-a1))
    Si += a1 - a0
tans = list(itertools.accumulate(tans))
for x, v in Mi:
    tans[x] += v
tans = list(itertools.accumulate(tans))
ans = [0]*m
for i, v in enumerate(tans):
    ans[i%m] += v
print(Si - max(ans))

import itertools
n,m=map(int,input().split())
a=list(map(int,input().split()))
s=[0]*(2*m+2)
tot=0
for l,r in zip(a,a[1:]):
	tot+=(r-l)%m
	if l>r:
		r+=m
	dif=r-l
	if dif>1:
		s[l+2]+=1
		s[r+1]-=dif
		s[r+2]+=dif-1
s=list(itertools.accumulate(list(itertools.accumulate(s))))
print(tot-max(s[i]+s[m+i] for i in a))

n,m=list(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)


N, M = list(map(int, input().split()))
a = list([int(x) - 1 for x in 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)



from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N,M = inpl()
aa = inpl()
for i in range(N):
	aa[i] -= 1

yama_height = [0]*(2*M)
yama_num = [0]*(2*M)
SUM = 0
for i in range(1,N):
	na = aa[i]
	ba = aa[i-1]
	if na < ba:
		na += M
	SUM += (na-ba)
	yama_height[na] += na - (ba + 1)
	yama_num[na] -= 1
	yama_num[ba+1] += 1

tmp = 0
for i in range(2*M):
	tmp += yama_num[i]
	yama_num[i] = tmp

ans_list = [0]*(M)
tmp = 0
for i in reversed(list(range(2*M))):
	tmp += yama_height[i]
	tmp -= yama_num[i]
	ans_list[i%M] += tmp

print((SUM-max(ans_list)))


import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import accumulate

n,m = li()
a = list(li_())

ans = [0]*m
# 1.前処理
# 1-1.a[1:]の中の x(0<= x < m)の個数
cnt_equal = [0]*m
for i in range(n-1):
    cnt_equal[a[i+1]] += (((a[i+1]+m-a[i])%m) - 1)

# 1-2.a[i]→a[i+1]の内側(両端除く)に x(0<= x < m)が入る回数
cnt_inner = [0]*(2*m+1)
for i in range(n-1):
    cnt_inner[a[i] + 1] += 1
    cnt_inner[a[i] + (a[i+1]+m-a[i])%m] -= 1
    
cnt_inner = list(accumulate(cnt_inner))
cnt_inner = [cnt_inner[i]+cnt_inner[i+m] for i in range(m)]


# 2.fav == 1 のときのシミュレーション
fav = 0
for i in range(n-1):
    ans[0] += min((a[i+1]+m-a[i])%m, 1+(a[i+1]+m-fav)%m)

# 3.favが[2,m]のとき、fav-1の情報をもとに更新
for fav in range(1,m):
    ans[fav] = ans[fav-1] + cnt_equal[fav-1] - cnt_inner[fav-1]
    
print(min(ans))