1011. 键盘杀手

题目描述

河灵的键盘又积灰了。河灵的键盘只有一排，共 n 个键帽，其中第 i 个键帽的高度为 ai。特

别地，我们认为键盘两侧各有一个高度为 0 的“空键帽”（即 a0 =

an+1 = 0）。

为了将键盘彻底清理干净，河灵需要将所有的键帽都拔下来。你可以进行若干次操作，每次操作形如：

• 选择一个正整数 i (1 ≤ i ≤ n)，将第 i 个键帽拔下来。由于拔键帽时会受到左右相邻位置键帽当前高度的影响，本次操作需要花费

max(ai−1, ai+1 ) 的代价，然后将 ai 赋值为 0，表示该位置的键帽

已被取下。注意，每次操作的代价取决于操作发生时左右相邻位置键帽的当前高度，而不是这些键帽的初始高度。请你帮帮河灵，求出将所有的键帽都拔下来的最小代价总和，即将

a1, a2, …, an 均赋值为 0 的最小代价总和。

输入格式

每个测试点中包含多组测试数据。输入的第一行包含一个正整数 T (

1 ≤ T ≤ 106 )，表示数据组数。对于每组测试数据：第一行一个正整数 n (1 ≤ n ≤ 105 )，表示序列长度。第二行 n 个正整数 a1, a2, …, an (1 ≤ ai ≤ 109 )，表示初始的序列 a

。保证所有测试数据中 n 之和不超过 106。

输出格式

对于每组测试数据：一行一个整数，表示最小代价总和。

样例输入

3
6
7 5 9 10 5 7
10
9 14 19 7 6 9 16 14 12 6
20
47 83 21 45 58 61 46 91 41 74 94 27 23 27 85 82 91
96 69 36

样例输出

23
60
596

来源：官方题面 PDF（2026"钉耙编程"暑期联赛 第2场）