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 翻译