A. Рассортировка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Назовем массив $$$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$$$ неотсортированным.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \leq n \leq 500$$$) — длину массива $$$a$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — массив $$$a$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$500$$$.

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

Выведите минимальное количество операций, необходимых для того, чтобы сделать массив неотсортированным.

Пример
Входные данные
4
2
1 1
4
1 8 10 13
3
1 3 2
3
1 9 14
Выходные данные
1
2
0
3
Примечание

В первом наборе мы можем выполнить $$$1$$$ операцию, чтобы сделать массив неотсортированным:

  • Выберем $$$i = 1$$$. Тогда $$$a$$$ становится равным $$$[2, 0]$$$, то есть перестаёт быть отсортированным.

Во втором случае мы можем выполнить $$$2$$$ операции, чтобы сделать массив неотсортированным:

  • Выберем $$$i = 3$$$. Тогда $$$a$$$ становится $$$[2, 9, 11, 12]$$$.
  • Выберем $$$i = 3$$$. Тогда $$$a$$$ становится $$$[3, 10, 12, 11]$$$, то есть он становится неотсортированным.

Можно доказать, что $$$1$$$ и $$$2$$$ операции являются минимальным необходимым количеством операций в первом и втором наборе соответственно.

В третьем случае массив уже неотсортирован, поэтому мы выполняем $$$0$$$ операций.