担任 Straightlineham 村的村长是一项真正的挑战。诚然，道路基础设施的开支微乎其微——所有 $n$ 名居民的房屋都按编号 $1$ 到 $n$ 沿穿过整个村庄的一条笔直道路排列。尽管如此，有时你仍需做出艰难的决定，例如发放开设酒吧的许可证。

事实证明，所有 Straightlineham 的居民都梦想着开设自己的酒吧。目前已提交了 $n$ 份申请表，每位居民一份。每位居民都提交了他们的商业计划，其中你最感兴趣的是酒吧开业后的拟议税额：第 $i$ 位居民承诺每位顾客向村庄缴纳 $p_i$ 枚金币。

你计划向一定数量（非空）的居民发放开设酒吧的许可证（甚至可以是所有人）。每位居民，无论是否获得开设自己酒吧的许可，都将成为另外两家酒吧的顾客：其房屋左侧最近的一家和右侧最近的一家（只要存在这样的酒吧——否则，该居民将成为较少酒吧的顾客）。在确定最近的酒吧时，我们不考虑该居民自己经营的酒吧——毕竟，最好的调酒师也不应该服务自己。在决定哪些酒吧开业后，每家酒吧将开始为村庄预算产生收入，每位顾客缴纳 $p_i$ 枚金币。例如，如果 $n = 5$ 且第三家和第五家酒吧开业，第一家将有 $4$ 位顾客，另一家有 $2$ 位顾客，产生的总税收收入为 $4 \cdot p_3 + 2 \cdot p_5$。

已知每家假设的酒吧承诺缴纳的税额，请确定通过以最优方式发放许可证所能获得的最大利润。

输入格式

输入的第一行包含测试用例的数量 $z$ ($1 \le z \le 10\,000$)。接下来是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($2 \le n \le 500\,000$)，即 Straightlineham 的居民人数。

每个测试用例的第二行包含 $n$ 个整数 $p_i$ ($1 \le p_i \le 10^9$)，即 $n$ 家假设酒吧中每家拟议的顾客税额。

所有测试用例的居民总数不超过 $3 \cdot 10^6$。

输出格式

对于每个测试用例，输出一个整数，表示通过最优发放许可证所能获得的最大总利润。

样例

样例输入 1

2
4
5 2 2 6
5
1 5 4 4 1

样例输出 1

33
29

说明

在第一个样例测试中，最优解是允许开设第一家和最后一家酒吧。它们每家都将拥有 $3$ 位顾客，从而产生 $3 \cdot 5 + 3 \cdot 6 = 33$ 枚金币的总收入。

在第二个样例测试中，最优解是允许开设除第三家以外的所有酒吧。在这种情况下，利润为 $1 \cdot 1 + 3 \cdot 5 + 3 \cdot 4 + 1 \cdot 1 = 29$。如果允许所有酒吧开业，利润会更小：$28$ 枚金币。