C. Омкар и водная горка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Омкар строит водную горку в своем аквапарке, и ему нужна ваша помощь, чтобы сделать это как можно эффективнее.

В настоящее время у Омкара есть $$$n$$$ опор, выстроенных в линию, $$$i$$$-я из которых имеет высоту $$$a_i$$$. Омкар хочет построить свою водную горку справа налево, поэтому его опоры должны быть неспадающими по высоте, чтобы выдержать водную горку. За $$$1$$$ операцию Омкар может сделать следующее: взять любой последовательный подотрезок опор, неспадающий по высотам, и добавить $$$1$$$ к высоте каждой из них.

Помогите Омкару найти минимальное количество операций, которые ему нужно сделать, чтобы его опоры смогли выдержать его водную горку!

Последовательность $$$b$$$ является подотрезком $$$c$$$, если $$$b$$$ может быть получена из $$$c$$$ удалением нескольких (возможно, ни одного или всех) элементов из начала и нескольких (возможно, ни одного или всех) элементов из конца.

Массив $$$b_1, b_2, \dots, b_n$$$ называется неспадающим, если $$$b_i\le b_{i+1}$$$ для каждого $$$i$$$ от $$$1$$$ до $$$n-1$$$.

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

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

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_{1},a_{2},...,a_{n}$$$ $$$(0 \leq a_{i} \leq 10^9)$$$ — высоты опор.

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

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

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

Пример
Входные данные
3
4
5 3 2 5
5
1 2 3 5 3
3
1 1 1
Выходные данные
3
2
0
Примечание

Подмассив, с которым Омкар выполняет операцию, выделен жирным шрифтом.

В первом наборе входных данных:

  • Первая операция:

    $$$[5, 3, \textbf{2}, 5] \to [5, 3, \textbf{3}, 5]$$$

  • Вторая операция:

    $$$[5, \textbf{3}, \textbf{3}, 5] \to [5, \textbf{4}, \textbf{4}, 5]$$$

  • Третья операция:

    $$$[5, \textbf{4}, \textbf{4}, 5] \to [5, \textbf{5}, \textbf{5}, 5]$$$

В третьем наборе входных данных массив уже является неспадающим, поэтому Омкар выполняет $$$0$$$ операций.