Назовем массив \(a\) длины \(n\) отсортированным, если \(a_1 \leq a_2 \leq \ldots \leq a_{n-1} \leq a_n\).
У Ntarsis есть массив \(a\) длины \(n\).
Он может выполнить следующую операцию над массивом любое число раз (в том числе ноль):
- Выбрать индекс \(i\) (\(1 \leq i \leq n-1\)).
- Добавить \(1\) к \(a_1, a_2, \ldots, a_i\).
- Вычесть \(1\) из \(a_{i+1}, a_{i+2}, \ldots, a_n\).
Значения \(a\) могут быть отрицательными после операции.
Определите минимальное количество операций, необходимых для того, чтобы сделать \(a\) неотсортированным.
Выходные данные
Выведите минимальное количество операций, необходимых для того, чтобы сделать массив неотсортированным.
Примечание
В первом наборе мы можем выполнить \(1\) операцию, чтобы сделать массив неотсортированным:
- Выберем \(i = 1\). Тогда \(a\) становится равным \([2, 0]\), то есть перестаёт быть отсортированным.
Во втором случае мы можем выполнить \(2\) операции, чтобы сделать массив неотсортированным:
- Выберем \(i = 3\). Тогда \(a\) становится \([2, 9, 11, 12]\).
- Выберем \(i = 3\). Тогда \(a\) становится \([3, 10, 12, 11]\), то есть он становится неотсортированным.
Можно доказать, что \(1\) и \(2\) операции являются минимальным необходимым количеством операций в первом и втором наборе соответственно.
В третьем случае массив уже неотсортирован, поэтому мы выполняем \(0\) операций.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2
1 1
4
1 8 10 13
3
1 3 2
3
1 9 14
|
1
2
0
3
|