310861: CF1901B. Chip and Ribbon

B. Chip and Ribbontime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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

Output

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

ExampleInput

4
4
1 2 2 1
5
1 0 1 0 1
5
5 4 3 2 1
1
12

Output

1
2
4
11

Note

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

题目大意：
有一个被分成n个单元格的彩带，从左到右编号为1到n。最初，每个单元格都写有一个整数0。Monocarp用一个芯片玩游戏。游戏由几轮组成。在第一轮中，Monocarp将芯片放在彩带的第1个单元格中。除了第一轮之外的每一轮，Monocarp都会执行以下两个动作中的一个：

1. 将芯片移动到下一个单元格（即如果芯片在单元格i中，则将其移动到单元格i+1）。如果芯片在最后一个单元格中，这个动作是无效的；
2. 选择任意单元格x并将芯片传送到该单元格。可以选择芯片当前所在的单元格。

每轮结束时，芯片所在单元格中写的整数增加1。

Monocarp的目标是通过进行一些轮次，使得第1个单元格包含整数c1，第2个单元格包含整数c2，...，第n个单元格包含整数cn。他希望尽可能少地传送芯片。

帮助Monocarp计算他必须传送芯片的最小次数。

输入输出数据格式：
输入：
第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。
每个测试用例包含两行：
- 第一行包含一个整数n（1≤n≤2×10^5）；
- 第二行包含n个整数c1,c2,...,cn（0≤ci≤10^9；c1≥1）。

输出：
对于每个测试用例，打印一个整数——Monocarp必须传送芯片的最小次数。

例：
输入：
4
4
1 2 2 1
5
1 0 1 0 1
5
5 4 3 2 1
1
12

输出：
1
2
4
11题目大意： 有一个被分成n个单元格的彩带，从左到右编号为1到n。最初，每个单元格都写有一个整数0。Monocarp用一个芯片玩游戏。游戏由几轮组成。在第一轮中，Monocarp将芯片放在彩带的第1个单元格中。除了第一轮之外的每一轮，Monocarp都会执行以下两个动作中的一个： 1. 将芯片移动到下一个单元格（即如果芯片在单元格i中，则将其移动到单元格i+1）。如果芯片在最后一个单元格中，这个动作是无效的； 2. 选择任意单元格x并将芯片传送到该单元格。可以选择芯片当前所在的单元格。 每轮结束时，芯片所在单元格中写的整数增加1。 Monocarp的目标是通过进行一些轮次，使得第1个单元格包含整数c1，第2个单元格包含整数c2，...，第n个单元格包含整数cn。他希望尽可能少地传送芯片。 帮助Monocarp计算他必须传送芯片的最小次数。 输入输出数据格式： 输入： 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。 每个测试用例包含两行： - 第一行包含一个整数n（1≤n≤2×10^5）； - 第二行包含n个整数c1,c2,...,cn（0≤ci≤10^9；c1≥1）。 输出： 对于每个测试用例，打印一个整数——Monocarp必须传送芯片的最小次数。 例： 输入： 4 4 1 2 2 1 5 1 0 1 0 1 5 5 4 3 2 1 1 12 输出： 1 2 4 11