CF1392C.Omkar and Waterslide

Omkar is building a waterslide in his water park, and he needs your help to ensure that he does it as efficiently as possible.

Omkar currently has $n$ supports arranged in a line, the $i$-th of which has height $a_i$. Omkar wants to build his waterslide from the right to the left, so his supports must be nondecreasing in height in order to support the waterslide. In $1$ operation, Omkar can do the following: take any contiguous subsegment of supports which is nondecreasing by heights and add $1$ to each of their heights.

Help Omkar find the minimum number of operations he needs to perform to make his supports able to support his waterslide!

An array $b$ is a subsegment of an array $c$ if $b$ can be obtained from $c$ by deletion of several (possibly zero or all) elements from the beginning and several (possibly zero or all) elements from the end.

An array $b_1, b_2, \dots, b_n$ is called nondecreasing if $b_i\le b_{i+1}$ for every $i$ from $1$ to $n-1$.

Omkar 正在他的水上乐园中建造一条水滑梯，他需要你的帮助，以确保以尽可能高效的方式完成建造。

Omkar 目前有 $n$ 根按直线排列的支撑柱，其中第 $i$ 根的高度为 $a_i$。Omkar 希望从右向左建造他的水滑梯，因此这些支撑柱的高度必须构成一个非递减序列，才能有效支撑水滑梯。在一次操作中，Omkar 可以执行以下操作：任选一个高度非递减的连续子段，并将该子段中所有支撑柱的高度均增加 $1$。

请帮助 Omkar 找出他所需的最少操作次数，使得支撑柱的高度能够支撑他的水滑梯！

数组 $b$ 是数组 $c$ 的一个子段（subsegment），当且仅当 $b$ 可通过从 $c$ 的开头删除若干个（可能为零个或全部）元素、并从 $c$ 的末尾删除若干个（可能为零个或全部）元素而得到。

数组 $b_1, b_2, \dots, b_n$ 被称为非递减的（nondecreasing），当且仅当对每个从 $1$ 到 $n-1$ 的 $i$，均有 $b_i \le b_{i+1}$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 100$). Description of the test cases follows.

The first line of each test case contains an integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the number of supports Omkar has.

The second line of each test case contains $n$ integers $a_{1},a_{2},...,a_{n}$ $(0 \leq a_{i} \leq 10^9)$ — the heights of the supports.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \leq t \leq 100$）。随后是测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$）—— Omkar 拥有的支撑柱数量。

每个测试用例的第二行包含 $n$ 个整数 $a_{1},a_{2},...,a_{n}$（$0 \leq a_{i} \leq 10^9$）—— 各支撑柱的高度。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

For each test case, output a single integer — the minimum number of operations Omkar needs to perform to make his supports able to support his waterslide.

对于每个测试用例，输出一个整数——Omkar 为使其支撑结构能够支撑他的水上滑梯所需的最少操作次数。

The subarray with which Omkar performs the operation is bolded.

In the first test case:

• First operation:

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

• Second operation:

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

• Third operation:

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

In the third test case, the array is already nondecreasing, so Omkar does $0$ operations.

Omkar 执行操作的子数组以粗体标出。

在第一个测试用例中：

• 第一次操作：

  $[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]$

在第三个测试用例中，数组本身已为非递减序列，因此 Omkar 执行 $0$ 次操作。