A. Возрастание по модулю
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У жабы Зитца есть массив целых чисел, каждое число в нем находится в пределах от $$$0$$$ до $$$m-1$$$ включительно. Это числа $$$a_1, a_2, \ldots, a_n$$$.

За одну операцию Зитц может выбрать целое число $$$k$$$ и $$$k$$$ таких индексов $$$i_1, i_2, \ldots, i_k$$$, что $$$1 \leq i_1 < i_2 < \ldots < i_k \leq n$$$. Затем он должен заменить $$$a_{i_j}$$$ на $$$((a_{i_j}+1) \bmod m)$$$ для каждого выбранного индекса $$$i_j$$$. Целое число $$$m$$$ фиксировано для всех операций и индексов.

Здесь $$$x \bmod y$$$ обозначает остаток от деления $$$x$$$ на $$$y$$$.

Зитц хочет сделать массив неубывающим за минимальное количество таких операций. Найдите это минимальное число операций.

Входные данные

В первой строке записано два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n, m \leq 300\,000$$$) — количество чисел в массиве и параметр $$$m$$$.

В следующей строке записаны $$$n$$$ целых чисел, разделенных пробелами $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i < m$$$) — данный массив.

Выходные данные

Выведите одно целое число: минимальное количество описанных операций, которое должен сделать Зитц, чтобы сделать его массив неубывающим. Если делать операций не требуется, выведите $$$0$$$.

Легко показать, что такими операциями Зитц всегда может сделать массив неубывающим.

Примеры
Входные данные
5 3
0 0 0 1 2
Выходные данные
0
Входные данные
5 7
0 6 1 3 2
Выходные данные
1
Примечание

В первом примере массив уже не убывает, поэтому ответ $$$0$$$.

Во втором примере вы можете выбрать $$$k=2$$$, $$$i_1 = 2$$$, $$$i_2 = 5$$$, массив станет $$$[0,0,1,3,3]$$$. Он неубывающий, поэтому ответ $$$1$$$.