У жабы Зитца есть массив целых чисел, каждое число в нем находится в пределах от \(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\).
Зитц хочет сделать массив неубывающим за минимальное количество таких операций. Найдите это минимальное число операций.
Выходные данные
Выведите одно целое число: минимальное количество описанных операций, которое должен сделать Зитц, чтобы сделать его массив неубывающим. Если делать операций не требуется, выведите \(0\).
Легко показать, что такими операциями Зитц всегда может сделать массив неубывающим.
Примечание
В первом примере массив уже не убывает, поэтому ответ \(0\).
Во втором примере вы можете выбрать \(k=2\), \(i_1 = 2\), \(i_2 = 5\), массив станет \([0,0,1,3,3]\). Он неубывающий, поэтому ответ \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 3
0 0 0 1 2
|
0
|
|
2
|
5 7
0 6 1 3 2
|
1
|