AT_arc229_f.Angst for All Pairs 2

You are given a positive integer $N$ and a length-$N$ sequence of positive integers $C=(C_1,C_2,\ldots,C_N)$.

You want to prepare one or more cards, as many as you like, and write one integer between $1$ and $N$ (inclusive) on each of the front and back sides of each card, so that the following condition is satisfied.

• No matter which distinct integers $x$ and $y$ between $1$ and $N$ (inclusive) are chosen, there exists at least one card satisfying the following.
  • Exactly one of $x$ and $y$ is written on at least one side of that card.

It is allowed to write the same integer on the front and back of a single card.

Here, the cost of writing $a$ on the front and $b$ on the back of a card is $C_a+C_b$.

Find the minimum total cost required to satisfy the condition.

You are given $T$ test cases; solve each of them.

给你一个正整数 $N$ 和一个长度为 $N$ 的正整数序列 $C=(C_1,C_2,\ldots,C_N)$。

你需要制作一张或多张卡片（数量不限），并在每张卡片的正面和背面各写一个介于 $1$ 到 $N$（含）之间的整数，使得满足以下条件：

• 对任意两个在 $1$ 到 $N$（含）范围内的不同整数 $x$ 和 $y$，都存在至少一张卡片，满足：
  • $x$ 和 $y$ 中恰好有一个出现在该卡片的至少一面（正面或背面）上。

允许在一张卡片的正面和背面写相同的整数。

这里，若在某张卡片的正面写 $a$、背面写 $b$，则其花费为 $C_a+C_b$。

求满足上述条件所需的最小总花费。

你将得到 $T$ 组测试数据；请分别求解每组数据。

The input is given from Standard Input in the following format:

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

Each test case is given in the following format:

$N$
$C_1$ $C_2$ $\ldots$ $C_N$

输入从标准输入给出，格式如下：

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

每个测试用例的格式如下：

$N$
$C_1$ $C_2$ $\ldots$ $C_N$

Output the answers for the test cases in order, separated by newlines.

按顺序输出测试用例的答案，答案之间用换行符分隔。

Sample 1 Explanation:
Consider the first test case.

By creating a card with $1$ written on the front and $2$ on the back, and a card with $2$ written on the front and $2$ on the back, the condition can be satisfied.

The total cost in this case is $3+2+2+2=9$. It is impossible to satisfy the condition with a total cost less than $9$, so output $9$ on the first line.

Constraints

• $1\le T\le 10^5$
• $2\le N\le 2\times 10^5$
• $1\le C_i\le 10^9$
• The sum of $N$ over all test cases is at most $2\times 10^5$.
• All input values are integers.

样例 1 解释：
考虑第一个测试用例。

通过制作一张正面写有 $1$、背面写有 $2$ 的卡片，以及一张正面写有 $2$、背面写有 $2$ 的卡片，即可满足条件。

此时总花费为 $3+2+2+2=9$。无法以低于 $9$ 的总花费满足条件，因此在第一行输出 $9$。

约束条件

• $1\le T\le 10^5$
• $2\le N\le 2\times 10^5$
• $1\le C_i\le 10^9$
• 所有测试用例的 $N$ 之和不超过 $2\times 10^5$。
• 所有输入值均为整数。