对撞器

Problem Description

有 $n$ 个柱子排成一排，其中从左到右第 $i$ 个柱子的高度为 $a_i$。在一次操作中，cats 可以选择一个未被移除的柱子，并将其移除。在移除后，其左侧和右侧分别与其距离最近的一个未被移除的柱子会发生碰撞。碰撞产生的能量为两者高度的 $max$。若其左侧或右侧不存在未被移除的柱子，则碰撞不会发生，产生的能量为 $0$。 cats 需要执行 $n$ 次操作，将全部的 $n$ 个柱子删除。你能帮 cats 求出这个过程中产生的能量总和的最大值吗？

Input

第一行包含一个整数 $T$ （$1\leq T \leq 2\cdot 10^4$），表示一共有 $T$ 组测试数据。 对于每组测试数据： 第一行为一个整数 $n$ （$1\leq n\leq 2\cdot 10^5$），表示柱子的总数。 第二行为 $n$ 个整数 $a_1,a_2,\dots a_n$ （$1\leq a_i \leq 10^9$），表示从左到右每个柱子的高度。 保证所有测试数据的 $n$ 之和不超过 $10^6$。

Output

对于每组测试数据，输出一个整数，表示删除过程中产生的能量总和的最大值。

Sample Input

6
1
142857
3
1 3 2
5
2 1 2 1 2
5
1 2 3 2 1
5
1 2 3 4 5
10
3 1 4 1 5 9 2 6 5 3

Sample Output

0
2
6
7
15
66

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（6）