← 返回题目列表

Codeforces · 1901/B

B. 芯片和色带

中文机器翻译题面 查看原题

有一个功能区,分为 $$$n$$$ 个单元格,从左到右编号为 $$$1$$$ 到 $$$n$$$。最初,每个单元格中写入一个整数$$$0$$$。

Monocarp 用芯片玩游戏。游戏由几个回合组成。在第一圈期间,Monocarp 将芯片放置在色带的 $$$1$$$-st 单元中。在除了第一回合之外的每个回合中,Monocarp 都会执行以下两个动作之一:

- 将筹码移动到下一个单元格(即,如果筹码位于单元格 $$$i$$$ 中,则将其移动到单元格 $$$i+1$$$ 中)。如果芯片位于最后一个单元格中,则无法执行此操作;
- 选择任何单元 $$$x$$$ 并将芯片传送到该单元中。可以选择芯片当前所在的单元格。

每回合结束时,写入芯片的单元格中的整数会增加$$$1$$$。

Monocarp 的目标是进行一些转弯,以便第 $$$1$$$-st 单元格包含整数 $$$c_1$$$,第 $$$2$$$-nd 单元格包含整数 $$$c_2$$$,...,第 $$$n$$$-th 单元格包含整数 $$$c_n$$$。他希望尽可能少地传送芯片。

帮助 Monocarp 计算他传送芯片的最少次数。

输入

第一行包含一个整数 $$$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$$$。

输出

对于每个测试用例,打印一个整数 — Monocarp 传送芯片的最小次数。

示例

输入 #1

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

输出 #1

1
2
4
11

注意

在示例的第一个测试用例中,Monocarp 可以执行如下转弯:

- 将芯片放入 $$$1$$$-st 单元格中;单元格中的数字为 $$$[1, 0, 0, 0]$$$;
- 将筹码移动到下一个($$$2$$$-nd)单元格;单元格中的数字为 $$$[1, 1, 0, 0]$$$;
- 将筹码移动到下一个($$$3$$$-rd)单元格;单元格中的数字为 $$$[1, 1, 1, 0]$$$;
- 将芯片传送到 $$$2$$$-nd 单元格;单元格中的数字为 $$$[1, 2, 1, 0]$$$;
- 将筹码移动到下一个($$$3$$$-rd)单元格;单元格中的数字为 $$$[1, 2, 2, 0]$$$;
- 将筹码移至下一个($$$4$$$)单元格;单元格中的数字为 $$$[1, 2, 2, 1]$$$。