AT_arc229_f [ARC229F] Angst for All Pairs 2

给定一个正整数 $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$ 组测试数据，请为每组测试数据输出答案。

输入通过标准输入给出，格式如下： > $T$ > $\text{case}_1$ > $\text{case}_2$ > $\vdots$ > $\text{case}_T$ 每组测试数据格式如下： > $N\ C_1\ C_2\ \ldots\ C_N$

按顺序为每组测试数据输出答案，每个答案占一行。

### 样例解释 1 考虑第一个测试用例。 可以制作一张卡片，正面写 $1$，反面写 $2$；再制作一张卡片，正、反两面都写 $2$，这样可以满足题目条件。 总花费为 $3+2+2+2=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$ - 输入均为整数。 由 ChatGPT 5 翻译