有 $n$ 个柱子排成一排，其中从左到右第 $i$ 个柱子的高度为 $a_i$。在一次操作中，cats 可以选择一个未被移除的柱子，并将其移除。在移除后，其左侧和右侧分别与其距离最近的一个未被移除的柱子会发生碰撞。碰撞产生的能量为两者高度的 $max$。若其左侧或右侧不存在未被移除的柱子，则碰撞不会发生，产生的能量为 $0$。

cats 需要执行 $n$ 次操作，将全部的 $n$ 个柱子删除。你能帮 cats 求出这个过程中产生的能量总和的最大值吗？

第一行包含一个整数 $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$。

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