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:
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.
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:
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$$$.
For each test case, print one integer — the minimum number of times Monocarp has to teleport the chip.
441 2 2 151 0 1 0 155 4 3 2 1112
1 2 4 11
In the first test case of the example, Monocarp can perform the turns as follows:
Name |
---|