Chip and Ribbon
Contest: Educational Codeforces Round 158 (Rated for Div. 2)
Difficulty rating: 1100
Tags: greedy, math

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 format:
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 format:
For each test case, print one integer — the minimum number of times Monocarp has to teleport the chip.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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

Example input:
4
4
1 2 2 1
5
1 0 1 0 1
5
5 4 3 2 1
1
12

Example output:
1
2
4
11

Editorial:
At first, let's change the statement a bit: instead of teleporting our chip into cell $$$x$$$, we create a new chip in cell $$$x$$$ (it means that the chip does not disappear from the cell where it was located). And when we want to move a chip, we move any chip to the next cell. Then, $$$c_i$$$ will be the number of times a chip appeared in the cell $$$i$$$, and the problem will be the same: ensure the condition on each $$$c_i$$$ by "creating" the minimum number of chips.
Let's look at value of $$$c_1$$$. If $$$c_1 > 1$$$, we have to create at least $$$c_1 - 1$$$ new chips in cell $$$1$$$. Let's create that number of chips in that cell.
Then, let's see how we move chips from the cell $$$i$$$ to the cell $$$(i+1)$$$. If $$$c_i \ge c_{i+1}$$$, then all chips that appeared in the cell $$$(i+1)$$$ could be moved from the $$$i$$$-th cell, so we don't need to create any additional chips in that cell.
But if $$$c_i < c_{i+1}$$$, then at least $$$c_{i+1} - c_i$$$ chips should be created in the cell $$$(i+1)$$$, since we can move at most $$$c_i$$$ chips from the left.
So, for every $$$i$$$ from $$$2$$$ to $$$n$$$, we have to create $$$\max(0, c_i - c_{i-1})$$$ chips in the $$$i$$$-th cell; and the number of times we create a new chip in total is $$$c_1 - 1 + \sum\limits_{i=2}^{n} \max(0, c_i - c_{i-1})$$$.