配点 : 100 点
致环球杯参赛者
当包含在 Universal Cup 中时,此问题将被删除。因此,当使用 AtCoder 结果进行 Universal Cup 时,我们建议先解决其他问题。 给出了
問題文
长度 小于或等于 N 的正整数序列 给出了 A = (A_1,A_2,\dots,A_N) 。 对于 A 执行以下操作 通过在 0 可以重复回避超过
- 整数 i \ (1 \le i \le N-1) 该值应乘以 1 选择 A_i, A_{i+1} 将两者 0 置换到这里。此操作的成本为 \max(A_i,A_{i+1}) 需要。
A 的所有元素 执行此操作所需的最少操作数(如果可以等于 0 求使其成为所需状态所需成本的最小和。
T 给出若干测试用例,请分别求出答案。
制約
- 1 \le T \le 10^5
- 2 \leq N \leq 2 \times 10^5
- 1 \le A_i \le 10^9
- 1 包含在输入文件中的 N 的总和是 2\times 10^5 以下
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
每个测试用例均按以下格式给出。 打印
N A_1 A_2 \cdots A_N
出力
T 行。i 在线 i 输出第几号测试用例的答案。
入力例 1
4 4 2 6 7 3 2 1 1000000000 20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 8 123 4567 8912 34 56789 12345 6789 1
出力例 1
12 1000000000 10 72647
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 。A=(0,0,0,0) 为了成为...而花费的成本的总和无法比这个更小,12 就是答案。 对于