Toad Zitz has an array of integers, each integer is between $0$ and $m-1$ inclusive. The integers are $a_1, a_2, \ldots, a_n$.

In one operation Zitz can choose an integer $k$ and $k$ indices $i_1, i_2, \ldots, i_k$ such that $1 \leq i_1 < i_2 < \ldots < i_k \leq n$. He should then change $a_{i_j}$ to $((a_{i_j}+1) \bmod m)$ for each chosen integer $i_j$. The integer $m$ is fixed for all operations and indices.

Here $x \bmod y$ denotes the remainder of the division of $x$ by $y$.

Zitz wants to make his array non-decreasing with the minimum number of such operations. Find this minimum number of operations.


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \leq n, m \leq 300\,000$) — the number of integers in the array and the parameter $m$.

The next line contains $n$ space-separated integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i < m$) — the given array.


-----Output-----

Output one integer: the minimum number of described operations Zitz needs to make his array non-decreasing. If no operations required, print $0$.

It is easy to see that with enough operations Zitz can always make his array non-decreasing.


-----Examples-----
Input
5 3
0 0 0 1 2

Output
0

Input
5 7
0 6 1 3 2

Output
1



-----Note-----

In the first example, the array is already non-decreasing, so the answer is $0$.

In the second example, you can choose $k=2$, $i_1 = 2$, $i_2 = 5$, the array becomes $[0,0,1,3,3]$. It is non-decreasing, so the answer is $1$.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Sorting

Greedy algorithms


Solutions:
import sys
(N, M) = map(int, input().split(' '))
A = list(map(int, sys.stdin.readline().split(' ')))

def check():
	last = 0
	for i in range(N):
		if A[i] < last:
			if last - A[i] > m:
				break
		elif A[i] > last:
			if A[i] + m < M or (A[i] + m) % M < last:
				last = A[i]
	else:
		return True
	return False
l = -1
r = M - 1
while l + 1 < r:
	m = (l + r) // 2
	if check():
		r = m
	else:
		l = m
print(r)


(n, m) = map(int, input().split())
arr = list(map(int, input().split()))
(l, r) = (0, m - 1)
while l < r:
	mid = (l + r) // 2
	p = 0
	f = True
	for x in arr:
		step = (m - x + p) % m
		if step > mid:
			if x < p:
				f = False
				break
			p = x
	if f is True:
		r = mid
	else:
		l = mid + 1
print(l)


from collections import Counter
from collections import defaultdict
from collections import deque
import math
import sys
input = sys.stdin.readline
import bisect
rs = lambda : input().strip()
ri = lambda : int(input())
rl = lambda : list(map(int, input().strip().split()))
rls = lambda : list(map(str, input().split()))

def check(k):
	p = []
	c = a[0]
	prev = 0
	for i in range(0, n):
		x1 = a[i]
		x2 = (a[i] + k) % m
		if x2 < x1:
			if x1 <= prev <= m - 1 or 0 <= prev <= x2:
				p.append(prev)
				continue
			else:
				prev = a[i]
		elif x2 > x1:
			if x1 <= prev <= x2:
				p.append(prev)
				continue
			elif x2 < prev:
				return -1
			else:
				prev = x1
		else:
			return -1
		p.append(prev)
	return 1
(n, m) = rl()
a = list(map(int, input().strip().split()))
if a == sorted(a):
	print(0)
	exit()
l = 0
r = m - 1
ans = m
while l <= r:
	mid = l + (r - l) // 2
	if check(mid) == 1:
		ans = min(mid, ans)
		r = mid - 1
	else:
		l = mid + 1
print(ans)


def checker(ij):
	count = 0
	for i in range(len(l)):
		if (count - l[i]) % m >= ij:
			if l[i] > count:
				count = l[i]
			else:
				return False
	return True
(n, m) = input().split()
(n, m) = [int(n), int(m)]
l = [int(i) for i in input().split()]
beg = -1
last = m
while beg < last - 1:
	mid = (beg + last) // 2
	counter = checker(mid)
	if counter:
		last = mid
	else:
		beg = mid
print(beg)


(n, m) = list(map(int, input().split()))
a = [int(i) for i in input().split()]
L = -1
R = m
while L < R - 1:
	mid = (L + R) // 2
	last = 0
	isok = True
	for el in a:
		if last == el:
			continue
		if last > el:
			if el + mid >= last:
				continue
			else:
				isok = False
				break
		elif el + mid - m >= last:
			continue
		else:
			last = el
	if isok:
		R = mid
	else:
		L = mid
print(R)


(n, m) = [int(i) for i in input().split()]
array = [int(i) for i in input().split()]

def bins(a, b):
	if a == b:
		return a
	mid = (a + b) // 2
	if good(mid):
		return bins(a, mid)
	else:
		return bins(mid + 1, b)

def good(k):
	arr = array[:]
	if arr[0] + k >= m:
		arr[0] = 0
	for i in range(1, n):
		if arr[i] < arr[i - 1]:
			if arr[i - 1] - arr[i] > k:
				return False
			else:
				arr[i] = arr[i - 1]
		elif arr[i] + k - m >= arr[i - 1]:
			arr[i] = arr[i - 1]
	return True
print(bins(0, m - 1))


def check(n, m, s, v):
	mi = 0
	for i in range(n):
		if v[i] + s < mi:
			return False
		if v[i] > mi:
			if (v[i] + s) % m >= mi:
				if v[i] <= (v[i] + s) % m:
					mi = v[i]
			else:
				mi = v[i]
	return True

def __starting_point():
	(n, m) = list(map(int, input().split()))
	v = list(map(int, input().split()))
	l = 0
	r = m
	while l < r:
		s = (l + r) // 2
		if check(n, m, s, v):
			r = s
		else:
			l = s + 1
	print(l)
__starting_point()


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
a = list(map(int, input().split()))

def isok(b, k):
	if b[0] + k >= m:
		b[0] = 0
	for i in range(len(a) - 1):
		if b[i + 1] > b[i]:
			if b[i + 1] + k >= m:
				if (b[i + 1] + k) % m >= b[i]:
					b[i + 1] = b[i]
		elif (b[i + 1] + k) % m >= b[i]:
			b[i + 1] = b[i]
		elif b[i + 1] + k >= b[i]:
			b[i + 1] = b[i]
		else:
			return False
	return True
left = -1
right = m
while right - left > 1:
	mid = left + (right - left) // 2
	if isok(a[:], mid):
		right = mid
	else:
		left = mid
print(right)


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

def chk(k):
	ret = 0
	for i in range(N):
		(a, b) = (A[i], (A[i] + k) % M)
		if a <= b < ret:
			return 0
		if ret <= a <= b or b < ret <= a:
			ret = a
	return 1
l = -1
r = M
while r - l > 1:
	m = (l + r) // 2
	if chk(m):
		r = m
	else:
		l = m
print(r)


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

def Check(x):
	y = 0
	for i in range(n):
		if a[i] <= y and a[i] + x >= y:
			continue
		elif a[i] + x >= m and a[i] + x - m >= y:
			continue
		elif a[i] + x < y:
			return False
		else:
			y = a[i]
	return True
ng = -1
ok = 10 ** 9
mid = 0
while abs(ok - ng) > 1:
	mid = (ok + ng) // 2
	if Check(mid):
		ok = mid
	else:
		ng = mid
print(ok)


import sys

def check(arr, n, m):
	k = len(arr)
	(low, high) = ([], [])
	for i in range(k):
		num = arr[i]
		if num + n < m:
			low.append([num, num + n])
			high.append([num, num + n])
		else:
			low.append([0, (num + n) % m])
			high.append([num, m - 1])
	lim = low[0][0]
	k = len(low)
	for i in range(1, k):
		if low[i][0] <= lim <= low[i][1]:
			continue
		if lim < low[i][0]:
			lim = low[i][0]
			continue
		if high[i][0] <= lim <= high[i][1]:
			continue
		if lim < high[i][0]:
			lim = high[i][0]
			continue
		return False
	return True
(n, m) = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
(low, high) = (0, m)
ans = 1000000
while low <= high:
	mid = (low + high) // 2
	if check(arr, mid, m):
		ans = min(ans, mid)
		high = mid - 1
	else:
		low = mid + 1
print(ans)


(n, m) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
left = 0
right = m
while right - left > 1:
	x = (right + left) // 2
	b = a[:]
	prev = 0
	for i in range(n):
		if b[i] < prev:
			if prev - b[i] <= x:
				b[i] = prev
			else:
				left = x
				break
		elif m - b[i] + prev <= x:
			b[i] = prev
		prev = b[i]
	else:
		right = x
if sorted(a) == a:
	print(0)
else:
	print(right)


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

def check(a, x, m):
	Max = m
	flg = True
	for val in a[::-1]:
		if val <= Max:
			Max = min(Max, val + x)
		elif val + x < m:
			flg = False
			break
		else:
			Max = min(Max, (val + x) % m)
	return flg
l = -1
u = m
while u - l > 1:
	md = (u + l) // 2
	if check(a, md, m) == True:
		u = md
	else:
		l = md
print(u)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
(l, r) = (0, m - 1)
while r > l:
	mid = l + r >> 1
	p = 0
	f = False
	for i in a:
		if i <= p <= i + mid or i <= p + m <= i + mid:
			continue
		if i < p:
			f = True
			break
		p = max(p, i)
	if f:
		l = mid + 1
	else:
		r = mid
print(r)


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
from collections import defaultdict
from itertools import permutations
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(N, M) = map(int, input().split())
A = [int(a) for a in input().split()]

def chk(k):
	ret = 0
	for i in range(N):
		(a, b) = (A[i], (A[i] + k) % M)
		if a <= b < ret:
			return 0
		if ret <= a <= b or b < ret <= a:
			ret = a
	return 1
l = -1
r = M
while r - l > 1:
	m = (l + r) // 2
	if chk(m):
		r = m
	else:
		l = m
print(r)


def inc_by_mod(arr, m):

	def is_opt(count):
		prev = 0
		for elem in arr:
			if prev < elem:
				if m - (elem - prev) > count:
					prev = elem
			elif prev - elem > count:
				return False
		return True
	count = 0
	(lo, hi) = (0, m - 1)
	while lo < hi:
		mid = lo + (hi - lo) // 2
		if is_opt(mid):
			hi = mid
		else:
			lo = mid + 1
	return lo

def main():
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	res = inc_by_mod(arr, m)
	print(res)
main()


(n, m) = input().split()
(n, m) = (int(n), int(m))
a = list(map(int, input().split()))
(l, r) = (0, m - 1)

def isOptimal(mid):
	prev = 0
	check = True
	for i in range(n):
		if prev < a[i]:
			if m - a[i] + prev > mid:
				prev = a[i]
		elif prev - a[i] > mid:
			check = False
	return check
while l <= r:
	check = True
	mid = (l + r) // 2
	prev = a[0]
	if isOptimal(mid):
		r = mid - 1
	else:
		l = mid + 1
check = isOptimal(l)
print(l * check + r * (not check))


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
sml = 0
big = m - 1
curr = (m - 1) // 2
while sml != big:
	bug = 0
	good = True
	for i in range(n):
		if a[i] + curr < m + bug:
			if a[i] + curr < bug:
				good = False
				break
			bug = max(bug, a[i])
	if good:
		big = max(curr, sml)
		curr = (big + sml) // 2
	else:
		sml = min(curr + 1, big)
		curr = (sml + big) // 2
print(curr)


def check(mid):
	p = 0
	for i in arr:
		if i < p and p - i > mid:
			return False
		if i > p and mid < p - i + m:
			p = i
	return True
(n, m) = map(int, input().split())
arr = list(map(int, input().split()))
(i, j) = (0, m)
ans = m
while i <= j:
	mid = i + (j - i) // 2
	if check(mid):
		ans = min(ans, mid)
		j = mid - 1
	else:
		i = mid + 1
print(ans)


import os
import sys
from io import BytesIO, IOBase

def check(a, mid, m, n):
	ma = m - 1
	for i in range(n - 1, -1, -1):
		if a[i] > ma:
			z = a[i] + mid
			if z >= m:
				ma = min(ma, z - m)
			else:
				return 0
		else:
			ma = min(a[i] + mid, ma)
	return 1

def main():
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	(lo, hi, ans) = (0, m, 0)
	while lo <= hi:
		mid = (lo + hi) // 2
		z = check(a, mid, m, n)
		if z:
			ans = mid
			hi = mid - 1
		else:
			lo = mid + 1
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
A = list(map(int, input().split()))
MIN = 0
MAX = m
while MIN != MAX:
	x = (MIN + MAX) // 2
	M = 0
	for a in A:
		if a <= M and a + x >= M:
			continue
		elif a > M and a + x >= m and ((a + x) % m >= M):
			continue
		elif a > M:
			M = a
		else:
			MIN = x + 1
			break
	else:
		MAX = x
print(MIN)


import sys
import math
from itertools import permutations
input = sys.stdin.readline
(n, m) = map(int, input().split())

def binarySearch(arr, l, r):
	if r >= l:
		mid = l + (r - l) // 2
		if l == r:
			return mid
		elif check(arr, mid):
			return binarySearch(arr, l, mid)
		else:
			return binarySearch(arr, mid + 1, r)
	else:
		return -1

def check(arr, x):
	now = arr[0]
	for i in range(len(arr)):
		if i == 0:
			if m - arr[i] <= x:
				now = 0
		elif arr[i] < now:
			if x >= now - arr[i]:
				now = now
			else:
				return False
		elif x >= (now - arr[i] + m) % m:
			now = now
		else:
			now = arr[i]
	return True
l = list(map(int, input().split()))
print(binarySearch(l, 0, m))


import math
import cmath
(n, m, v) = (0, 0, [])

def solve():
	nonlocal m, v
	(st, dr) = (0, m - 1)
	while st < dr:
		md = st + dr >> 1
		ok = 1
		cur = 0
		for x in v:
			if x + md >= m:
				if cur >= x or cur <= x + md - m:
					continue
				else:
					cur = int(x)
			elif cur > x + md:
				ok = 0
				break
			elif cur < x:
				cur = int(x)
		if ok == 1:
			dr = md
		else:
			st = md + 1
	return st

def main():
	nonlocal n, m, v
	(n, m) = (int(x) for x in input().split())
	v = list((int(x) for x in input().split()))
	ans = solve()
	print(ans)

def __starting_point():
	main()
__starting_point()


(N, M) = map(int, input().split())
A = list(map(int, input().split()))
L = -1
R = M
while L < R - 1:
	mid = (L + R) // 2
	last = 0
	k = 1
	for i in A:
		if last == i:
			continue
		if last > i:
			if i + mid >= last:
				continue
			else:
				k = 0
				break
		elif i + mid - M >= last:
			continue
		else:
			last = i
	if k == 1:
		R = mid
	else:
		L = mid
print(R)


import heapq
import sys
import bisect
from collections import defaultdict
from itertools import product
(n, m) = list(map(int, input().split()))
arr = list(map(int, input().split()))
(l, r) = (-1, m)

def check_v(v):
	M = 0
	for el in arr:
		if el <= M:
			if el + v >= M:
				continue
			else:
				return False
		elif el + v >= M + m:
			continue
		else:
			M = el
	return True
while r - l > 1:
	mid = (l + r) // 2
	if check_v(mid):
		r = mid
	else:
		l = mid
print(r)


def check(mid, arr, n, m):
	prev = 0
	for i in range(n):
		if arr[i] > prev:
			t = m - (arr[i] - prev)
			if t > mid:
				prev = arr[i]
		else:
			t = prev - arr[i]
			if t > mid:
				return False
	return True
(n, m) = map(int, input().split())
arr = list(map(int, input().split()))
lo = 0
hi = m
while lo <= hi:
	mid = (lo + hi) // 2
	if check(mid, arr, n, m):
		ans = mid
		hi = mid - 1
	else:
		lo = mid + 1
print(ans)


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

def check(k):
	pre = 0
	for a in A:
		if a == pre:
			continue
		elif a < pre:
			if a + k < pre:
				return False
		else:
			if a + k >= M and (a + k) % M >= pre:
				continue
			pre = a
	return True
ok = M
ng = -1
while abs(ok - ng) > 1:
	med = (ok + ng) // 2
	if check(med):
		ok = med
	else:
		ng = med
print(ok)


(n, k) = map(int, input().split())
A = list(map(int, input().split()))
l = 0
r = k + 1
ans = k + 1
for _ in range(20):
	B = [0] * n
	m = (l + r) // 2
	min1 = 0
	fl = 0
	for i in range(n):
		if A[i] > min1:
			if k - A[i] + min1 <= m:
				B[i] = min1
			else:
				min1 = A[i]
				B[i] = A[i]
		elif min1 - A[i] > m:
			fl = 1
			break
		else:
			B[i] = min1
	if fl == 0:
		for i in range(n - 1):
			if B[i] > B[i + 1]:
				break
				fl = 1
		if fl == 0:
			r = m
			ans = min(ans, m)
		else:
			l = m
	else:
		l = m
print(ans)


from sys import stdin
(n, m) = map(int, stdin.readline().strip().split())
s = list(map(int, stdin.readline().strip().split()))
high = m + 1
low = 0
while high - low > 1:
	mx = 0
	flag = True
	mid = (low + high) // 2
	for i in range(n):
		if s[i] >= mx:
			if s[i] + mid >= m and (s[i] + mid) % m >= mx:
				continue
			else:
				mx = s[i]
		elif s[i] + mid >= mx:
			continue
		else:
			flag = False
			break
	if flag:
		high = mid
	else:
		low = mid
for j in range(low, low + 2):
	mx = 0
	flag = True
	mid = (j + j + 1) // 2
	for i in range(n):
		if s[i] >= mx:
			if s[i] + mid >= m and (s[i] + mid) % m >= mx:
				continue
			else:
				mx = s[i]
		elif s[i] + mid >= mx:
			continue
		else:
			flag = False
			break
	if flag:
		print(j)
		break


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
lo = 0
hi = m
mid = (lo + hi) // 2
while lo < hi:
	minupto = 0
	anw = 0
	for i in range(n):
		if a[i] < minupto:
			anw = max(minupto - a[i], anw)
		elif a[i] + mid >= m and (a[i] + mid) % m >= minupto:
			pass
		else:
			minupto = a[i]
	if anw > mid:
		lo = mid + 1
	else:
		hi = mid
	mid = (lo + hi) // 2
print(mid)


import sys

def input():
	return sys.stdin.readline().rstrip()

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

	def minimum(K, v, lower_bound):
		if v >= lower_bound:
			if m + lower_bound - v <= K:
				return lower_bound
			else:
				return v
		elif lower_bound - v >= K:
			return v + K
		else:
			return lower_bound

	def possible(K):
		if K < 0:
			return False
		V = 0
		for v in a:
			nextV = minimum(K, v, V)
			if V <= nextV:
				V = nextV
			else:
				return False
		return True
	l = -1
	r = m * m + 10
	while r - l > 1:
		med = (r + l) // 2
		if possible(med):
			r = med
		else:
			l = med
	print(r)
	return

def main():
	t = 1
	for i in range(t):
		slv()
	return
main()


def check(mid):
	local_a = [0]
	for ai in a:
		local_a.append(ai)
	for i in range(1, n + 1):
		if local_a[i] < local_a[i - 1]:
			if local_a[i] + mid >= local_a[i - 1]:
				local_a[i] = local_a[i - 1]
		elif local_a[i] + mid >= m + local_a[i - 1]:
			local_a[i] = local_a[i - 1]
		if local_a[i] < local_a[i - 1]:
			return False
	return True
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
(low, high) = (0, m)
while low != high:
	mid = low + high >> 1
	if check(mid):
		high = mid
	else:
		low = mid + 1
print(low)


def main():
	(n, m) = map(int, input().split())
	a = tuple(map(int, input().split()))
	(l_, r) = (-1, m - 1)
	while l_ + 1 < r:
		m_ = (l_ + r) // 2
		ai1 = 0
		for ai in a:
			if (m + ai1 - ai) % m > m_:
				if ai < ai1:
					l_ = m_
					break
				ai1 = ai
		else:
			r = m_
	print(r)
main()


from sys import stdin, stdout
from math import *
(n, m, a) = (0, 0, [])

def test(k):
	global n, m, a
	b = []
	for i in range(n):
		b.append(a[i])
		if i == 0:
			if b[i] + k >= m:
				b[i] = 0
		else:
			if b[i] == b[i - 1]:
				continue
			if b[i - 1] > b[i]:
				if b[i - 1] <= b[i] + k:
					b[i] = b[i - 1]
			elif b[i] + k >= m and b[i - 1] <= (b[i] + k) % m:
				b[i] = b[i - 1]
			if b[i - 1] > b[i]:
				return False
	return True

def main():
	global n, m, a
	(n, m) = [int(x) for x in stdin.readline().split()]
	a = [int(x) for x in stdin.readline().split()]
	res = m
	l = 0
	r = m
	while l <= r:
		mid = floor((l + r) / 2)
		if test(mid) == True:
			res = min(res, mid)
			r = mid - 1
		else:
			l = mid + 1
	stdout.write(str(res))
	return 0
main()


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

def done(a):
	return all((x < y for (x, y) in zip(a[:-1], a[1:])))
maxops = m - 1
minops = 0
while maxops > minops:
	cops = (maxops + minops) // 2
	base = 0
	ok = True
	for a in ass:
		if base > a and base - a > cops:
			ok = False
			break
		elif (base - a) % m > cops:
			base = a
	if ok:
		maxops = cops
	else:
		minops = cops + 1
print(maxops)


import sys
import math
import collections
import heapq
input = sys.stdin.readline
(n, m) = (int(i) for i in input().split())
l = [int(i) for i in input().split()]
le = -1
ri = m
while le < ri - 1:
	mid = (le + ri) // 2
	prev = 0
	c = 1
	for i in range(n):
		if (m - l[i] + prev) % m > mid:
			if l[i] < prev:
				c = 0
				break
			else:
				prev = l[i]
	if c == 0:
		le = mid
	else:
		ri = mid
print(ri)


import sys
import math as mt
input = sys.stdin.buffer.readline
t = 1

def check(x1):
	prev = 0
	for i in range(n):
		if arr[i] > prev:
			x = m - (arr[i] - prev)
			if x > x1:
				prev = arr[i]
		if arr[i] < prev:
			x = prev - arr[i]
			if x > x1:
				return False
	return True
for _ in range(t):
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	(l, r) = (0, m)
	ans = m
	while 1 < r - l:
		mid = (l + r) // 2
		if check(mid):
			ans = min(ans, mid)
			r = mid
		else:
			l = mid
	if check(ans - 1):
		ans -= 1
	print(ans)


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

def can(h):
	B = []
	last = 0
	for i in range(0, n):
		b = A[i]
		if b <= last:
			if last - b <= h:
				continue
			else:
				return False
		else:
			if m - b + last <= h:
				continue
			last = b
		B.append(b)
	return True
left = 0
right = m
while left < right:
	middle = (left + right) // 2
	if can(middle):
		right = middle
	else:
		left = middle + 1
print(left)


import sys, math

def read_int():
	return int(sys.stdin.readline().strip())

def read_int_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def read_string():
	return sys.stdin.readline().strip()

def read_string_list(delim=' '):
	return sys.stdin.readline().strip().split(delim)
(n, m) = read_int_list()
arr = read_int_list()

def is_ok(maxi):
	global arr
	prev = 0
	for i in range(len(arr)):
		if prev <= arr[i]:
			k = prev + m - arr[i]
			if k > maxi:
				prev = arr[i]
		else:
			k = prev - arr[i]
			if k > maxi:
				return 0
	return 1
(l, r) = (0, m)
while l <= r:
	mid = l + (r - l) // 2
	if is_ok(mid):
		r = mid - 1
	else:
		l = mid + 1
if is_ok(l):
	print(l)
else:
	print(r)


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

def Check(x):
	y = 0
	for i in range(n):
		if a[i] <= y and a[i] + x >= y:
			continue
		elif a[i] + x >= m and a[i] + x - m >= y:
			continue
		elif a[i] + x < y:
			return False
		else:
			y = a[i]
	return True
l = 0
r = 10 ** 9
(mid, ans) = (0, 0)
while l <= r:
	mid = (l + r) // 2
	if Check(mid):
		r = mid - 1
		ans = mid
	else:
		l = mid + 1
print(ans)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
(l, r, ans) = (0, m, m)
while l <= r:
	mid = (l + r) // 2
	cur = 0 if a[0] + mid >= m else a[0]
	i = 1
	while i < n:
		if a[i] + mid < cur:
			break
		if not (a[i] < cur or (a[i] + mid >= m and (a[i] + mid) % m >= cur)):
			cur = a[i]
		i += 1
	if i == n:
		ans = min(ans, mid)
		if l == r:
			break
		r = mid
	else:
		if l == r:
			break
		l = mid + 1
print(ans)


import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys
from typing import List

def solve(N, M, A):

	def check(ops):
		pv = 0
		for v in A:
			if v + ops < M:
				if v + ops < pv:
					return False
				pv = max(pv, v)
			else:
				d = (v + ops) % M
				if d >= pv:
					pass
				else:
					pv = max(pv, v)
		return True
	(lo, hi) = (0, max(N, M))
	while lo <= hi:
		m = (lo + hi) // 2
		if check(m):
			hi = m - 1
		else:
			lo = m + 1
	return lo
(N, M) = map(int, input().split())
A = [int(x) for x in input().split()]
print(solve(N, M, A))


import sys

class Main:

	def __init__(self):
		self.buff = None
		self.index = 0

	def next(self):
		if self.buff is None or self.index == len(self.buff):
			self.buff = self.next_line()
			self.index = 0
		val = self.buff[self.index]
		self.index += 1
		return val

	def next_line(self):
		return sys.stdin.readline().split()

	def next_ints(self):
		return [int(x) for x in sys.stdin.readline().split()]

	def next_int(self):
		return int(self.next())

	def solve(self):
		(n, m) = self.next_ints()
		x = self.next_ints()
		low = 0
		high = m
		while high - low > 1:
			mid = (high + low) // 2
			if self.test(mid, x, m):
				high = mid
			else:
				low = mid
		print(low if self.test(low, x, m) else high)

	def test(self, st, xs, m):
		xx = 0
		for x in xs:
			fr = x
			to = x + st
			if to >= m:
				to -= m
			if to >= fr:
				if xx > to:
					return False
				xx = max(xx, fr)
			elif to < xx < fr:
				xx = fr
		return True
Main().solve()


def check(times, nums, m):
	current = 0 if nums[0] + times >= m else nums[0]
	for i in range(1, len(nums)):
		if nums[i] == current:
			continue
		if nums[i] < current and current - nums[i] > times:
			return False
		if nums[i] > current and m - nums[i] + current > times:
			current = nums[i]
	return True

def main():
	(n, m) = [int(x) for x in input().split()]
	nums = [int(x) for x in input().split()]
	if check(0, nums, m):
		return 0
	l = 0
	r = m
	while l + 1 < r:
		mid = (l + r) // 2
		if check(mid, nums, m):
			r = mid
		else:
			l = mid
	return r
print(main())


def modulo(a, maxi, n, m):
	prev = 0
	for i in range(n):
		if a[i] > prev:
			t = m - (a[i] - prev)
			if t > maxi:
				prev = a[i]
		else:
			t = prev - a[i]
			if t > maxi:
				return False
	return True
(n, m) = map(int, input().split())
arr = list(map(int, input().split()))
l = 0
r = m
while l <= r:
	mid = (l + r) // 2
	if modulo(arr, mid, n, m):
		ans = mid
		r = mid - 1
	else:
		l = mid + 1
print(ans)


def f(x):
	curr = 0
	for i in range(n):
		if curr >= m:
			return 0
		if x < m - arr[i]:
			if arr[i] + x < curr:
				return 0
			curr = max(curr, arr[i])
		else:
			start = (x + arr[i]) % m
			if curr > start:
				curr = max(curr, arr[i])
	return 1

def binary_search(l, r):
	mid = (l + r) // 2
	if l == r:
		return mid
	if f(mid):
		if f(mid - 1) == 0:
			return mid
		return binary_search(l, mid - 1)
	return binary_search(mid + 1, r)
l = input().split()
n = int(l[0])
m = int(l[1])
l = input().split()
arr = [int(i) for i in l]
print(binary_search(0, m - 1))


from sys import stdin
ii = lambda : int(input())
mi = lambda : map(int, input().split())
li = lambda : list(mi())
si = lambda : input()
msi = lambda : map(int, stdin.readline().split())
lsi = lambda : list(msi())
(n, m) = li()
a = li()
(l, r) = (0, m)
while l < r:
	M = (l + r) // 2
	ai1 = 0
	for ai in a:
		if (m - ai + ai1) % m > M:
			if ai < ai1:
				l = M + 1
				break
			ai1 = ai
	else:
		r = M
print(l)


(n, m) = [int(i) for i in input().split()]
array = [int(i) for i in input().split()]
a = 0
b = m - 1
while a < b:
	mid = (a + b) // 2
	ret = True
	q = mid - m
	last = array[0]
	if last + q >= 0:
		last = 0
	for i in range(1, n):
		d = last - array[i]
		if d > mid:
			ret = False
			break
		if d <= 0 and d > q:
			last = array[i]
	if ret:
		b = mid
	else:
		a = mid + 1
print(a)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
(l, r) = (-1, m - 1)
while l + 1 < r:
	(mid, p, f) = ((l + r) // 2, 0, 1)
	for i in a:
		if (m - i + p) % m > mid:
			if i < p:
				f = 0
				break
			p = i
	if f:
		r = mid
	else:
		l = mid
print(r)


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

def enough(mid):
	prev = l[0]
	if m - l[0] <= mid:
		prev = 0
	for i in range(1, len(l)):
		if prev > l[i]:
			if prev - l[i] > mid:
				return False
		elif m - l[i] + prev > mid:
			prev = l[i]
	return True

def bs():
	(l, r) = (0, m - 1)
	while l < r:
		mid = (l + r) // 2
		if enough(mid):
			r = mid
		else:
			l = mid + 1
	return r
print(bs())


from sys import stdin

def input():
	return stdin.readline().strip()

def solve(beg, end, a, MOD):
	if beg + 1 == end:
		return end
	k = (beg + end) // 2
	conditions = []
	prev = 0
	flag = True
	for i in range(n):
		if k + a[i] < MOD:
			cond = [(a[i], a[i] + k)]
		elif k + a[i] >= MOD:
			cond = [(a[i], MOD - 1), (0, (a[i] + k) % MOD)]
		if len(cond) == 2:
			if prev >= cond[0][0] and prev <= cond[0][1]:
				prev = prev
			elif prev >= cond[1][0] and prev <= cond[1][1]:
				prev = prev
			elif prev <= min(cond[0][0], cond[1][0]):
				prev = min(cond[0][0], cond[1][0])
			elif prev <= max(cond[0][0], cond[1][0]):
				prev = max(cond[0][0], cond[1][0])
			else:
				flag = False
				break
		elif prev <= cond[0][0]:
			prev = cond[0][0]
		elif prev >= cond[0][0] and prev <= cond[0][1]:
			prev = prev
		else:
			flag = False
			break
	if not flag:
		return solve(k, end, a, MOD)
	else:
		if beg == k:
			return k
		return solve(beg, k, a, MOD)
(n, MOD) = map(int, input().split())
a = list(map(int, input().split()))
print(solve(-1, MOD, a, MOD))


def ok(a, arr):
	prev = 0
	for i in range(n):
		if prev <= arr[i]:
			s = m + prev - arr[i]
			if s > a:
				prev = arr[i]
		else:
			s = prev - arr[i]
			if s > a:
				return False
	return True
(n, m) = map(int, input().split(' '))
arr = [int(i) for i in input().split(' ')]
l = -1
r = m
while r - l > 1:
	mid = int((r + l) / 2)
	if ok(mid, arr):
		r = mid
	else:
		l = mid
print(r)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, m) = map(int, input().split())
l = list(map(int, input().split()))

def check(k):
	prev = 0
	i = 0
	while i < n:
		s = prev - l[i]
		if s < 0:
			s += m
		if s <= k:
			i += 1
		else:
			prev += 1
		if prev == m:
			return False
	return True

def binarySearch():
	l = 0
	r = m - 1
	mid = (l + r) // 2
	while l < r:
		if check(mid) == True:
			r = mid
		else:
			l = mid + 1
		mid = (l + r) // 2
	return mid
print(binarySearch())


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
v = list(map(int, input().split()))
lo = -1
hi = m
while lo + 1 < hi:
	mid = (hi + lo) // 2
	prev = 0
	ok = 1
	for i in v:
		if i < prev:
			if i + mid < prev:
				ok = 0
				break
		elif i > prev:
			if m - i + prev > mid:
				prev = i
	if ok:
		hi = mid
	else:
		lo = mid
print(hi)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
(l, r) = (0, m)
ans = 0
while l <= r:
	mid = l + r >> 1
	(prev, bad) = (0, False)
	for i in a:
		if (prev - i + m) % m <= mid:
			continue
		elif i >= prev:
			prev = i
		elif i < prev:
			bad = True
			break
	if bad:
		l = mid + 1
	else:
		r = mid - 1
		ans = mid
print(ans)


import sys
input = sys.stdin.readline

def main():
	(N, M) = map(int, input().split())
	A = list(map(int, input().split()))
	l = 0
	r = M
	m = (l + r) // 2
	while l < r:
		ok = True
		pre = 0
		for a in A:
			p = []
			if a <= pre <= a + m:
				continue
			elif pre < a:
				if a + m - M >= pre:
					continue
				else:
					pre = a
			else:
				ok = False
		if ok:
			if r == m:
				break
			r = m
			m = (l + r) // 2
		else:
			if l == m:
				break
			l = m
			m = (l + r) // 2
	print(r)
main()


import os
import sys
from io import BytesIO, IOBase
_str = str
BUFSIZE = 8192

def str(x=b''):
	return x if type(x) is bytes else _str(x).encode()

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def inp():
	return sys.stdin.readline().rstrip()

def mpint():
	return map(int, inp().split(' '))

def itg():
	return int(inp())

def discrete_binary_search(func, lo, hi):
	while lo < hi:
		mi = lo + (hi - lo) // 2
		if func(mi):
			hi = mi
		else:
			lo = mi + 1
	return lo

def solve():
	(n, m) = mpint()
	arr = tuple(mpint())

	def check(x):
		prev = 0
		for i in range(n):
			if arr[i] > prev:
				if m - (arr[i] - prev) > x:
					prev = arr[i]
			elif prev - arr[i] > x:
				return False
		return True
	return discrete_binary_search(check, 0, m)

def main():
	print(solve())
DEBUG = 0
URL = 'https://codeforces.com/contest/1169/problem/C'
if DEBUG:
	if DEBUG == 2:
		main()
		exit()
	import requests
	from ACgenerator.Y_Test_Case_Runner import TestCaseRunner
	runner = TestCaseRunner(main, URL)
	inp = runner.input_stream
	print = runner.output_stream
	runner.checking()
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
	main()


def chek(mid):
	v = 0
	for i in range(n):
		if (v - a[i]) % m > mid:
			if a[i] > v:
				v = a[i]
			else:
				return False
	return True
(n, m) = list(map(int, input().split()))
l = -1
r = m
a = list(map(int, input().split()))
chek(3)
while l < r - 1:
	mid = (l + r) // 2
	if chek(mid):
		r = mid
	else:
		l = mid
print(r)


(n, m) = map(int, input().split())
a = tuple(map(int, input().split()))
(l, r) = (-1, m - 1)
while l + 1 < r:
	M = (l + r) // 2
	ai1 = 0
	for ai in a:
		if (m - ai + ai1) % m > M:
			if ai < ai1:
				l = M
				break
			ai1 = ai
	else:
		r = M
print(r)


import copy
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
l = -1
r = 300001

def check(x):
	success = True
	last = 0 if a[0] + x >= m else a[0]
	for i in range(1, n):
		now = a[i]
		if now < last:
			now = min(last, now + x)
		if a[i] + x >= m + last:
			now = last
		if now < last:
			return False
		last = now
	return True
while r - l > 1:
	mid = (l + r) // 2
	if check(mid):
		r = mid
	else:
		l = mid
print(r)


def isenough(m, a, mid):
	b = 0
	k = 0
	for i in a:
		if b < i:
			if m - i + b > mid:
				b = i
		if b > i:
			if i + mid < b:
				return False
	return True
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
low = -1
high = m
while low + 1 < high:
	mid = low + (high - low) // 2
	if isenough(m, a, mid) == False:
		low = mid
	else:
		high = mid
print(high)


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

def check(x):
	if ns[0] + x >= m:
		minn = 0
	else:
		minn = ns[0]
	for i in range(1, n):
		c = ns[i]
		if minn >= c:
			if c + x >= minn:
				continue
			else:
				return False
		elif c + x < m:
			minn = c
			continue
		elif (c + x) % m >= minn:
			continue
		else:
			minn = c
	return True
p = True
for i in range(n - 1):
	if ns[i + 1] < ns[i]:
		p = False
		break
if p:
	print(0)
	quit()
(l, r) = (0, m - 1)
while r - l > 1:
	mm = (r + l) // 2
	if check(mm):
		r = mm
	else:
		l = mm
print(r)


def check(M):
	now = 0
	for i in range(n):
		if (now - mas[i]) % m > M:
			if mas[i] > now:
				now = mas[i]
			else:
				return False
	return True
(n, m) = list(map(int, input().split()))
l = -1
r = m
mas = list(map(int, input().split()))
check(3)
while l < r - 1:
	M = (l + r) // 2
	if check(M):
		r = M
	else:
		l = M
print(r)