Migrated from Lutece 3026 想要沉溺于 Hack 陷阱

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

东科大（东京科技大学）是世界信息安全专业最强大学之一，也是世界上所有未成年天才黑客的神醉心往之处。

然而，这些天才们的问题在于，他们总是过于沉溺于黑入其他人的设施所带来的成就感，被这种感觉深深俘虏，无法自拔。

“黑入他人设施的感觉让我怦然心动。”

——一名东科大的学生如是说道。

总是无法自拔地寻找一切目标实施骇入，或许这就是爱情的盲目吧。

“可是，亲爱的，像这样花心搭讪可不行哦，小心网警找上门~”

---

东科大有 $n$ 间宿舍，从左到右按 $1$ 到 $n$ 编号。

（为了避免一些歧义，这里默认一间宿舍等于一个同学）

每间宿舍都签约了具有固定带宽的有线网络，其中第 $i$ 间宿舍的有线网络带宽为 $p_i$ $(p_i>0)$。

有些宿舍会给自己宿舍的网络开 WiFi 接入点。但是，一旦这样做了，就难逃被其他宿舍黑进 WiFi 偷带宽的命运。

为了尽量减少干扰，每个宿舍只会偷左右两边除了自家网络之外距离最近的 WiFi 网络。具体地，如果左右两边只有一边存在其他宿舍的 WiFi 网络，那么他们就只偷存在 WiFi 的那一边最近的那个 WiFi；否则，他们会同时偷左边最近的和右边最近的这两个 WiFi 网络。

（注：同学们自己宿舍的 WiFi 接入点本身不会增加偷得的网络的带宽，因为他们是用自己的手机偷 WiFi 而不是用路由器偷 WiFi。即，如果 B 偷了 A 的网络，C 又偷了 B 的网络，那么 C 并不会传递性地偷到 A 的网络）

一个同学总是会认为自己偷到的带宽就是他偷到的所有 WiFi 网络的签约带宽之和，尽管其实一个 WiFi 可能同时被很多人偷。但总之，只要一个同学自己认为自己偷到的带宽越多，他获得的成就感就会越高。这里我们进一步定义：一个同学获得的成就感等于他认为他偷到的带宽总和。

现在每个宿舍都还没有确定他们宿舍要不要开 WiFi 接入点。辅导员 Natsuzora 非常关心同学们的幸福程度，因此，请你帮他计算一下，在最优情况下，同学们获得的成就感之和最大是多少。

Input

第一行一个整数 $t$ $(1\le t\le 10^4)$，表示数据组数；

对于每组数据：

第一行一个整数 $n$ $(2\le n\le 10^6)$，表示宿舍的间数；

第二行 $n$ 个整数，其中第 $i$ 个整数表示第 $i$ 间宿舍的签约带宽 $p_i$ $(1\le p_i\le 10^9)$。

数据保证 $\sum n\le 10^6$。

Output

对于每组数据，输出一行一个整数，表示同学们获得的成就感之和的最大值。

Samples

1
6
1 1 4 5 1 4

37

Note

样例解释：

在第 $1$、$3$、$4$、$6$ 间宿舍开 WiFi 接入点，则每间宿舍同学获得的成就感分别为 $4+5+6+8+9+5=37$。可以证明没有更优的方案。

---

$\text{}$ アイワナムチュー - MAISONdes/asmi/すりぃ

Resources

2023 UESTC ICPC Training for Mathematics