题目描述

河灵的键盘又积灰了。

河灵的键盘只有一排，共 $n$ 个键帽，其中第 $i$ 个键帽的高度为 $a_i$。特别地，我们认为键盘两侧各有一个高度为 $0$ 的"空键帽"（即 $a_0 = a_{n+1} = 0$）。

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

• 选择一个正整数 $i$（$1 \le i \le n$），将第 $i$ 个键帽拔下来。由于拔键帽时会受到左右相邻位置键帽当前高度的影响，本次操作需要花费 $\max(a_{i-1}, a_{i+1})$ 的代价，然后将 $a_i$ 赋值为 $0$，表示该位置的键帽已被取下。

注意，每次操作的代价取决于操作发生时左右相邻位置键帽的当前高度，而不是这些键帽的初始高度。

请你帮帮河灵，求出将所有的键帽都拔下来的最小代价总和，即将 $a_1, a_2, \ldots, a_n$ 均赋值为 $0$ 的最小代价总和。

输入格式

每个测试点中包含多组测试数据。第一行包含一个正整数 $T$（$1 \le T \le 10^6$），表示数据组数。对于每组测试数据：

• 第一行一个正整数 $n$（$1 \le n \le 10^5$），表示序列长度。
• 第二行 $n$ 个正整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$），表示初始的序列 $a$。

保证所有测试数据中 $n$ 之和不超过 $10^6$。

输出格式

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

输入输出样例

样例输入 #1

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

样例输出 #1

23
60
596

说明/提示

约束条件

• $1 \le T \le 10^6$
• $1 \le n \le 10^5$
• $1 \le a_i \le 10^9$
• 所有测试数据中 $n$ 之和不超过 $10^6$
• 所有输入值均为整数。