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

Дан массив целых чисел $$$a$$$ длины $$$n$$$.

Вы можете применить следующую операцию любое количество раз (возможно, нулевое):

  • Сначала выбрать натуральное $$$k$$$ такое, что $$$1 \le k \le n$$$, и заплатить $$$k + 1$$$ монету.
  • Потом выбрать ровно $$$k$$$ индексов $$$1 \le i_1 < i_2 < \ldots < i_k \le n$$$.
  • После этого, для каждого $$$x$$$ от $$$1$$$ до $$$k$$$, увеличить $$$a_{i_x}$$$ на $$$1$$$.

Найдите минимальное количество монет, необходимых для того, чтобы сделать массив $$$a$$$ неубывающим, то есть $$$a_1 \le a_2 \le \ldots \le a_n$$$.

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

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

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

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

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

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

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

Пример
Входные данные
5
3
1 7 9
5
2 1 4 7 6
4
1 3 2 4
1
179
9
344 12 37 60 311 613 365 328 675
Выходные данные
0
3
2
0
1821
Примечание

В первом наборе входных данных массив $$$a$$$ уже отсортирован, поэтому ответ ноль.

Во втором наборе входных данных оптимальная последовательность операций это:

  • Выбрать $$$k = 2$$$ и индексы $$$2$$$ и $$$5$$$: $$$[ 2, \color{red}{1}, 4, 7, \color{red}{6} ] \rightarrow [2, 2, 4, 7, 7]$$$. Это стоит $$$3$$$ монеты.
Можно доказать, что невозможно сделать $$$a$$$ неубывающим, потратив меньше чем $$$3$$$ монеты.