CF1901B Chip and Ribbon

有一条带子被分成了 $n$ 个格子，从左到右编号为 $1$ 到 $n$。最初，每个格子里都写着整数 $0$。 Monocarp 和一个棋子玩游戏。游戏包含若干回合。在第一回合，Monocarp 将棋子放在第 $1$ 个格子上。在除第一回合外的每一回合，Monocarp 恰好执行以下两种操作之一： - 将棋子移动到下一个格子（即如果棋子在第 $i$ 个格子，则移动到第 $i+1$ 个格子）。如果棋子在最后一个格子，则无法执行此操作； - 选择任意一个格子 $x$，并将棋子传送到该格子。可以选择棋子当前所在的格子。 每回合结束时，棋子所在格子里的整数加 $1$。 Monocarp 的目标是通过若干回合，使得第 $1$ 个格子里的整数为 $c_1$，第 $2$ 个格子里的整数为 $c_2$，……，第 $n$ 个格子里的整数为 $c_n$。他希望尽可能少地传送棋子。 请你帮助 Monocarp 计算他至少需要传送棋子多少次。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例包含两行： - 第一行包含一个整数 $n$（$1 \le n \le 2 \times 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 \times 10^5$。

对于每个测试用例，输出一个整数，表示 Monocarp 至少需要传送棋子多少次。

以样例的第一个测试用例为例，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]$。 由 ChatGPT 4.1 翻译