AtCoder Regular Contest 077 - guruguru

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.

Source: atcoder | Difficulty: HARD


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


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


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)


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) = 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(ans + v)


import sys
input = sys.stdin.readline
import itertools
(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)
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
	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
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)


(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
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]
ans -= res
print(ans)


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


class BIT:

	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 + 1
		s = 0
		while i <= self.n:
			s += self.bit[i]
			i += i & -i
		return s

	def add(self, 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))


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


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)


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


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)


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


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


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

def __starting_point():
	C()
__starting_point()


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


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
a0 = a[0]
DDF = [0 for _ in range(m)]
A = [m - 1]
for i in range(1, n):
	A.append((a[i] - a0 - 1) % m)
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]:
		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
for i in range(1, m):
	DDF[i] = DDF[i - 1] + DDF[i]
for i in range(1, m):
	DDF[i] = DDF[i - 1] + DDF[i]
print(total_step - max(DDF))


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)


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


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


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(range(2 * M)):
	tmp += yama_height[i]
	tmp -= yama_num[i]
	ans_list[i % M] += tmp
print(SUM - max(ans_list))


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


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 acc(X):
	return list(accumulate(X))
(N, M) = map(int, input().split())
A = [int(a) - 1 for a in input().split()]
X = [0] * M
Y = [0] * M

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)

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()
ans -= max(X)
print(ans)


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


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


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


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


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
(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)
	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
temp = ans
for x in range(1, max(A)):
	for p in prev[x]:
		temp += (x - p) % M - 1
	temp -= S[x]
	ans = min(ans, temp)
print(ans)


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


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

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

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

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

	def sett(self, i, x):
		self.add(i, x - self.sum(i, i + 1))

	def print_bit(self):
		print([self.sum(i, i + 1) for i in range(self.size)])

	def print_sum(self):
		print([self.sum(0, i + 1) for i in range(self.size)])

	def lower_bound_left(self, w):
		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):
		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):
		return self.upper_bound_left(w) - 1

	def upper_bound_right(self, w):
		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)
S = [B.sum(0, i + 1) for i in range(3 * m)]
for i in range(1, 3 * m):
	S[i] += S[i - 1]
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()))
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)


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


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


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


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


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


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


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


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


(n, m) = map(int, input().split())
a_list = list(map(int, input().split()))
bonus_str_cnt = [0] * (m + 1)
bonus_end_vol = [0] * (m + 1)
bonus_end_cnt = [0] * (m + 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))


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)


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


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)


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
cnt_equal = [0] * m
for i in range(n - 1):
	cnt_equal[a[i + 1]] += (a[i + 1] + m - a[i]) % m - 1
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)]
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)
for fav in range(1, m):
	ans[fav] = ans[fav - 1] + cnt_equal[fav - 1] - cnt_inner[fav - 1]
print(min(ans))


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


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


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


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


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


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


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


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


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