题目内容

云侧在做双资源池隔离验收时，会给每个实例挂一整型重要度权重。现有 $n$ 个实例，第 $i$ 个实例的权重记为 $v_i$。你需要给每个实例再赋一个整型优先级 $r_i$，并据此连出一张 $n$ 个点的无向图（点编号 $1\sim n$）。

对任意 $1\le i < j\le n$：

• 若 $r_i > r_j$，则在 $i,j$ 之间连边，边权为 $v_j$；
• 若 $r_j > r_i$，则在 $i,j$ 之间连边，边权为 $v_i$；
• 若 $r_i = r_j$，则不连边。

也就是说：仅当两点优先级不同时才连边，边权等于优先级更低那一侧实例的权重。

图必须连通。在连通前提下，求所有边权之和的最大可能值。可以证明解一定存在。

连通图：任意两点之间都存在路径。

输入描述

第一行一个整数 $q$（$1\le q\le 10000$），表示询问个数。

接下来共 $q$ 组询问，每组格式如下：

• 第一行一个整数 $n$（$1\le n\le 200000$），表示实例个数；
• 第二行 $n$ 个整数 $v_1,v_2,\ldots,v_n$（$-n\le v_i\le n$），表示各实例权重。

保证单个文件中所有询问的 $n$ 之和不超过 $200000$。

输出描述

对每个询问输出一行一个整数，表示最大边权之和。

样例1

输入

3
4
4 1 -2 3
3
0 -3 -1
5
2 5 1 4 3

输出

19
0
40

说明

第 $1$ 个询问：权重从大到小为 $4,3,1,-2$。给 $4,3$ 更低且互不相同的优先级，给 $1,-2$ 相同的最高优先级，贡献 $4\times 3 + 3\times 2 = 19$。

第 $2$ 个询问：全部非正，取最大值 $0$ 单独作为较低优先级，答案 $0\times 2=0$。

第 $3$ 个询问：全部为正，按从大到小赋递增优先级，贡献 $5\times 4+4\times 3+3\times 2+2\times 1=40$。