连锁能量核心

题目描述

在一条能量通道中排列着 $n$ 个连续的能量节点，从左到右编号为 $1 \sim n$。 部分节点中嵌入了能量核心，可以通过手动激活或连锁反应被激活。

• 若第 $i$ 个节点的参数为 $a_i > 0$，表示该节点存在一个能量核心，手动激活它需要消耗 $a_i$ 单位能量；
• 若 $a_i = 0$，表示该节点为空，不存在能量核心。

一旦某个能量核心被激活（无论是手动激活，还是被其他核心触发）：

• 会立刻尝试激活它左右相邻节点中的能量核心（即位置 $i-1$ 和 $i+1$）；
• 被激活的核心会继续触发新的连锁反应；
• 该过程会持续进行，直到无法激活新的核心为止。

⚠️ 每个能量核心只会被激活一次。

你可以选择任意一些能量核心进行手动激活，其余的依靠连锁反应完成。

请你计算：激活所有能量核心所需的最小总能量消耗。

正式的，给你一个整数序列 $a_1, a_2, \dots, a_n$，其中 $a_i$ 表示手动激活第 $i$ 个能量核心所需的能量消耗。 当这个核心被激活，它会触发与之相邻的能量核心的激活，直到当前的能量核心的值为 $0$ 时停止。 你需要选择一些能量核心进行手动激活，使得所有能量核心最终都被激活，并且总的激活能量消耗最小。

输入格式

第一行输入一个整数 $T（1 \le T \le 10^4）$，表示测试数据组数。

接下来对于每组数据：

• 第一行输入一个整数 $n（1 \le n \le 2 \times 10^6）$，表示能量节点数量；
• 第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n（0 \le a_i \le 10^9）$。

保证：

• 单个测试文件中所有测试用例的 $n$ 之和不超过 $2 \times 10^6$。

输出格式

对于每组测试数据，输出一行一个整数，表示最小能量消耗。

样例 1

2
5
2 0 3 3 4
6
0 0 1 0 0 2

5
3

提示

对于第一组样例：核心位置在 1、3、4、5，花费分别为 2、3、3、4，手动激活位置 1 和 3 即可，总消耗为 5。