← 返回题目列表

Codeforces · 1705/B

B. 标记除尘器

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

马克正在打扫一排 $$$n$$$ 房间。第 $$$i$$$ 个房间的灰尘级别为非负值 $$$a_i$$$。他有一台神奇的清洁机,可以进行以下三步操作。

- 选择两个索引 $$$i<j$$$,使得灰尘级别 $$$a_i$$$、$$$a_{i+1}$$$、$$$\dots$$$、$$$a_{j-1}$$$ 都严格大于 $$$0$$$。
- 将 $$$a_i$$$ 设置为 $$$a_i-1$$$。
- 将 $$$a_j$$$ 设置为 $$$a_j+1$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1\leq t\leq 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2\leq n\leq 2\cdot 10^5$$$) — 房间数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$0\leq a_i\leq 10^9$$$) — 每个房间的灰尘级别。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,打印一行包含单个整数 - 最小操作数。可以证明存在满足目标的操作序列。

示例

输入 #1

4
3
2 0 0
5
0 2 0 2 0
6
2 0 3 0 4 6
4
0 0 0 10

输出 #1

3
5
11
0

注意

在第一种情况下,一个可能的操作顺序如下。

- 选择 $$$i=1$$$ 和 $$$j=2$$$,生成数组 $$$[1,1,0]$$$。
- 选择 $$$i=1$$$ 和 $$$j=3$$$,生成数组 $$$[0,1,1]$$$。
- 选择 $$$i=2$$$ 和 $$$j=3$$$,生成数组 $$$[0,0,2]$$$。

在第二种情况下,一种可能的操作顺序如下。

- 选择 $$$i=4$$$ 和 $$$j=5$$$,生成数组 $$$[0,2,0,1,1]$$$。
- 选择 $$$i=2$$$ 和 $$$j=3$$$,生成数组 $$$[0,1,1,1,1]$$$。
- 选择 $$$i=2$$$ 和 $$$j=5$$$,生成数组 $$$[0,0,1,1,2]$$$。
- 选择 $$$i=3$$$ 和 $$$j=5$$$,生成数组 $$$[0,0,0,1,3]$$$。
- 选择 $$$i=4$$$ 和 $$$j=5$$$,生成数组 $$$[0,0,0,0,4]$$$。

在最后一种情况下,数组已经满足条件。