AT_tupc2024_p.Adjacent Reset

给定一个长度为 $N$ 的正整数序列 $A = (A_1, A_2, \dots, A_N)$。可以对 $A$ 重复进行如下操作 $0$ 次或多次：

• 选择一个整数 $i\ (1 \le i \le N-1)$，将 $A_i, A_{i+1}$ 都替换为 $0$。该操作的代价为 $\max(A_i, A_{i+1})$。

请你求出将 $A$ 的所有元素都变为 $0$ 所需最小总代价。

给定 $T$ 个测试用例，请分别输出每个测试用例的答案。

输入按以下格式从标准输入读入：

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

每个测试用例如下格式：

$N\ A_1\ A_2\ \cdots\ A_N$

请输出 $T$ 行，第 $i$ 行输出第 $i$ 个测试用例的答案。

致 Universal Cup 参赛者

本题在收录至 Universal Cup 时将被删除。因此，如果你需要在 AtCoder 的结果用于 Universal Cup，建议先做除本题以外的问题。

样例解释 1

对于第 $1$ 个测试用例，例如可以按如下方式进行 $3$ 次操作：

• 对 $A=(2,6,7,3)$ 执行 $i=2$ 的操作，$A=(2,0,0,3)$，代价为 $7$。
• 对 $A=(2,0,0,3)$ 执行 $i=1$ 的操作，$A=(0,0,0,3)$，代价为 $2$。
• 对 $A=(0,0,0,3)$ 执行 $i=3$ 的操作，$A=(0,0,0,0)$，代价为 $3$。

总代价为 $7+2+3=12$。无法获得更小的代价，因此 $12$ 是答案。

数据范围

• $1 \le T \le 10^5$
• $2 \leq N \leq 2 \times 10^5$
• $1 \le A_i \le 10^9$
• 每份输入文件中所有 $N$ 的总和不超过 $2\times 10^5$
• 输入均为整数。

由 ChatGPT 5 翻译