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$ .

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$ .

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.

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.