← 返回题目列表

AtCoder · tupc2024_p

P. 相邻重置

中文机器翻译题面 查看原题

配点 : 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 就是答案。 对于