有一个楼梯,由 $$$n$$$ 级台阶组成。每一步要么完好无损,要么破损。对于每个损坏的步骤,给出一个整数 $$$a_i$$$ 表示修复它的难度。
每天,您可以:
- 修复任意损坏的步骤。修复第 $$$i$$$ 步骤所需的工作量等于 $$$a_i$$$;
- 或修复两个相邻损坏的台阶。修复第 $$$i$$$ 步骤和第 $$$(i+1)$$$ 步骤所需的工作量等于 $$$2 \cdot (a_i+a_{i+1})$$$。
您想要修复楼梯上所有破损的台阶,并且希望在尽可能短的时间内完成。在最少的天数内修复所有损坏的台阶至少需要多少工作量?
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例由两行组成:
- 第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — 步数;
- 第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^8$$$)。如果$$$a_i = 0$$$,则第$$$i$$$步不需要修复;否则,第$$$i$$$步骤被破坏,并且$$$a_i$$$是修复它的难度。
对输入的附加约束:$$$n$$$ 的值之和不超过 $$$3 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 在最短的天数内修复所有损坏的步骤所需的最小可能的总工作量。
示例
输入 #1
6 5 0 0 0 0 0 4 0 13 15 8 4 13 15 0 8 8 1 2 3 4 5 6 7 8 5 99999999 100000000 99999999 99999999 99999999 5 2 3 4 3 2
输出 #1
0 59 64 72 899999993 24
注意
在第一个测试用例中,您无需执行任何操作。
在第二个测试用例中,您可以在第一天修复 $$$3$$$-rd 和 $$$4$$$-th 步骤,并在第二天修复 $$$2$$$-nd 步骤。总工作量将为 $$$2 \cdot (15 + 8) + 13 = 59$$$。
在第三个测试用例中,您可以在第一天修复第 $$$4$$$ 步骤,并在第二天修复两个第一步。总工作量将为 $$$8 + 2 \cdot (13 + 15) = 64$$$。