马克正在打扫一排 $$$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]$$$。
在最后一种情况下,数组已经满足条件。