有一个功能区,分为 $$$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]$$$。