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$.

Difficulty: competition

Starter code:

Solutions:
import sys
input = sys.stdin.readline

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


MIN=0
MAX=m

while MIN!=MAX:
    x=(MIN+MAX)//2
    #print(x,MIN,MAX)
    #print()

    M=0
    for a in A:
        #print(a,M)
        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)


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

# AC
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(next(self))

    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


def __starting_point():
    Main().solve()

__starting_point()

#
n, m = list(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)
        else:
            if (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)        
        


from sys import stdin
n,m=list(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 = 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]
            else:
                if 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))


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

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)



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
        else:
            if el + mid - m >= last:
                continue
            else:
                last = el
    if isok:
        R = mid
    else:
        L = mid
print(R)


n, m = 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
        else:
            if el + mid - m >= last:
                continue
            else:
                last = el
    if isok:
        R = mid
    else:
        L = mid
print(R)

"""
observations:
1. multi solution

"""


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)

def __starting_point():
    main()
__starting_point()

def check(M):
    now = 0
    for i in range(n):
        #print(i, now, mas[i], M, (now - mas[i]) % m)
        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)

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
		# print(l, r, mid)
		if check(mid, nums, m):
			r = mid
		else:
			l = mid
	return r


def __starting_point():
	print(main())
__starting_point()

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(l, r)
print(r)


def checker(ij):
    count=0
    for i in range(len(l)):
        #print(count)
        #print(((count-l[i])%m),ij)
        if ((count-l[i])%m)>=ij:
            if l[i]>count:
                count=l[i]
            else:
                return False
    #print(l)
    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)
    #print(beg,last)
    if counter:
        last=mid
    else:
        beg=mid
print(beg)


#First we notice that the number of overall operations is equal to the maximum number
#of operations used on a single index.Next we notice that, if we can solve the problem
#in <= X operations, then we can also solve it in <= X + 1 operations.
#This is a monotonic sequence, so we can solve for the minimum value of X with binary search.
#we have to check wether each element can be changed into
#its previous element(count) in the list using a specified number of operations
#if its not possible then we have to check wether current element is greater
#than the previosu element , if it is so, then we have no need to change
#as the list is already in non decreaing form, then we simply replace
#count with the current element
#if it is lesser than count, then there is no way to make the element
#greater than or equal to the previous element using specified number of
#operations and we return to the binary search part to get the next no. of
#operations
def checker(ij):
    count=0
    for i in range(len(l)):
        #print(count)
        #print(((count-l[i])%m),ij)
        if ((count-l[i])%m)>=ij:
            if l[i]>count:
                count=l[i]
            else:
                return False
    #print(l)
    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)
    #print(beg,last)
    if counter:
        last=mid
    else:
        beg=mid
print(beg)


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)

# -*- coding: utf-8 -*-

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

"""
created by shhuan at 2020/1/14 22:22

"""


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 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)
            else:
                if(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()

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]

		# print(i, mi)
	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):
			# print(s, 1)
			r = s
		else:
			# print(s, 0)
			l = s+1

	print(l)

__starting_point()

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

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]
            else:
                if 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()))
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
        else:
            if i + mid - M >= last:
                continue
            else:
                last = i
    if k == 1:
        R = mid
    else:
        L = mid
print(R)