B. Сделайте зигзагообразным
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Произвольный массив целых чисел $$$b$$$ длины $$$m$$$ называется замечательным, если для всех $$$i$$$ ($$$1 \le i \lt m$$$):

  • если $$$i$$$ нечетное, то выполняется $$$b_i \lt b_{i + 1}$$$.
  • если $$$i$$$ четное, то выполняется $$$b_i \gt b_{i + 1}$$$.

Другими словами, выполняется следующее неравенство: $$$b_1 \lt b_2 \gt b_3 \lt b_4 \ldots$$$

Вам дан массив целых положительных чисел $$$a$$$ длины $$$n$$$. Вы можете выполнять любую из следующих операций любое количество раз и в любом порядке:

  • операция $$$1$$$: выберите целое число $$$i$$$ ($$$1 \le i \le n$$$) и выполните: $$$a_i := \max(a_1,\ldots,a_i)$$$, то есть замените $$$a_i$$$ на максимальное значение префикса до $$$i$$$ включительно.
  • операция $$$2$$$: выберите целое число $$$i$$$ ($$$1 \le i \le n$$$) и уменьшите $$$a_i$$$ на $$$1$$$.

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

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

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

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — длина массива $$$a$$$.

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

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите минимальную стоимость, чтобы сделать массив $$$a$$$ замечательным.

Пример
Входные данные
7
5
1 4 2 5 3
4
3 3 2 1
5
6 6 6 6 6
7
1 2 3 4 5 6 7
3
3 2 1
2
1 2
9
65 85 19 53 21 79 92 29 96
Выходные данные
0
1
3
6
1
0
13
Примечание

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

Во втором наборе входных данных массив $$$a$$$ можно сделать замечательным следующим образом:

  • используйте операцию $$$2$$$ и уменьшите $$$a_1$$$ на $$$1$$$. $$$[\color{red}3, 3, 2, 1] \rightarrow [\color{red}2, 3, 2, 1]$$$.
  • используйте операцию $$$1$$$ и измените $$$a_4$$$ на $$$\max(2, 3, 2, 1) = 3$$$. $$$[2, 3, 2, \color{red}1] \rightarrow [2, 3, 2, \color{red}3]$$$.
$$$[2, 3, 2, 3]$$$ является замечательным, так как $$$2 \lt 3 \gt 2 \lt 3$$$. Можно доказать, что это минимальное количество раз, которое нужно выполнить операцию $$$2$$$.