CF1901B.Chip and Ribbon

There is a ribbon divided into $n$ cells, numbered from $1$ to $n$ from left to right. Initially, an integer $0$ is written in each cell.

Monocarp plays a game with a chip. The game consists of several turns. During the first turn, Monocarp places the chip in the $1$-st cell of the ribbon. During each turn except for the first turn, Monocarp does exactly one of the two following actions:

• move the chip to the next cell (i. e. if the chip is in the cell $i$, it is moved to the cell $i+1$). This action is impossible if the chip is in the last cell;
• choose any cell $x$ and teleport the chip into that cell. It is possible to choose the cell where the chip is currently located.

At the end of each turn, the integer written in the cell with the chip is increased by $1$.

Monocarp's goal is to make some turns so that the $1$-st cell contains the integer $c_1$, the $2$-nd cell contains the integer $c_2$, ..., the $n$-th cell contains the integer $c_n$. He wants to teleport the chip as few times as possible.

Help Monocarp calculate the minimum number of times he has to teleport the chip.

有一条被划分为 $n$ 个格子的丝带，格子从左到右编号为 $1$ 到 $n$。初始时，每个格子中均写有整数 $0$。

Monocarp 用一枚棋子进行一场游戏。游戏由若干轮组成。在第一轮中，Monocarp 将棋子放在丝带的第 $1$ 个格子中。在除第一轮外的每一轮中，Monocarp 恰好执行以下两种操作之一：

• 将棋子移至下一个格子（即：若棋子当前位于第 $i$ 个格子，则将其移至第 $i+1$ 个格子）。若棋子已位于最后一个格子，则此操作不可行；
• 任选一个格子 $x$，并将棋子瞬移至该格子。可以选择棋子当前所在的格子。

每轮结束时，棋子所在格子中的整数增加 $1$。

Monocarp 的目标是经过若干轮操作后，使得第 $1$ 个格子中包含整数 $c_1$，第 $2$ 个格子中包含整数 $c_2$，……，第 $n$ 个格子中包含整数 $c_n$。他希望尽可能减少瞬移操作的次数。

请帮助 Monocarp 计算所需的最少瞬移次数。

The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Each test case consists of two lines:

• the first line contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$);
• the second line contains $n$ integers $c_1, c_2, \dots, c_n$ ($0 \le c_i \le 10^9$; $c_1 \ge 1$).

It can be shown that under these constraints, it is always possible to make a finite amount of turns so that the integers in the cells match the sequence $c_1, c_2, \dots, c_n$.

Additional constraint on the input: the sum of values of $n$ over all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 表示测试用例的数量。

每个测试用例由两行组成：

• 第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）；
• 第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$（$0 \le c_i \le 10^9$；且 $c_1 \ge 1$）。

在给定约束条件下，可以证明：总存在有限步操作，使得格子中的整数恰好变为序列 $c_1, c_2, \dots, c_n$。

输入的附加约束：所有测试用例中 $n$ 的值之和不超过 $2 \cdot 10^5$。

For each test case, print one integer — the minimum number of times Monocarp has to teleport the chip.

对于每个测试用例，输出一个整数——Monocarp 需要传送棋子的最少次数。

In the first test case of the example, Monocarp can perform the turns as follows:

• place the chip in the $1$-st cell; the numbers in the cells are $[1, 0, 0, 0]$;
• move the chip to the next ($2$-nd) cell; the numbers in the cells are $[1, 1, 0, 0]$;
• move the chip to the next ($3$-rd) cell; the numbers in the cells are $[1, 1, 1, 0]$;
• teleport the chip to the $2$-nd cell; the numbers in the cells are $[1, 2, 1, 0]$;
• move the chip to the next ($3$-rd) cell; the numbers in the cells are $[1, 2, 2, 0]$;
• move the chip to the next ($4$-th) cell; the numbers in the cells are $[1, 2, 2, 1]$.

在示例的第一个测试用例中，Monocarp 可以按如下方式执行操作：

• 将棋子放置在第 $1$ 个格子中；各格子中的数字为 $[1, 0, 0, 0]$；
• 将棋子移动到下一个（第 $2$ 个）格子；各格子中的数字为 $[1, 1, 0, 0]$；
• 将棋子移动到下一个（第 $3$ 个）格子；各格子中的数字为 $[1, 1, 1, 0]$；
• 将棋子瞬移到第 $2$ 个格子；各格子中的数字为 $[1, 2, 1, 0]$；
• 将棋子移动到下一个（第 $3$ 个）格子；各格子中的数字为 $[1, 2, 2, 0]$；
• 将棋子移动到下一个（第 $4$ 个）格子；各格子中的数字为 $[1, 2, 2, 1]$。