题目描述

本题与 G 题不同，在本题中您必须在最多一次的操作后输出前缀最小值的最小和。

给定一个整数 $n$ 与一个长度为 $n$ 的数组 $a(0\leq a_i \leq n)$，可以执行以下操作：

• 选择两个整数 $i,j(i<j)$。令 $a_i = a_i + a_j$，同时令 $a_j=0$。

需要注意的是，上面的操作只能执行最多一次。

输出可能的 $\min(a_1)+\min(a_1,a_2)+\ldots+\min(a_1,a_2,\ldots,a_n)$ 的最小值。

输入格式

每个测试包含多个测试用例。

测试数据的第一行为一个整数 $t(1\leq t\leq 10^4)$，表示测试用例的组数。

每组测试用例共两行，第一行为一个整数 $n(2\leq n\leq2\times10^5)$。

第二行为 $n$ 个整数，表示题目中的数组 $a$。

测试数据保证所有 $n$ 的和不超过 $2\times10^5$。

输出格式

对于每一组测试用例，输出可能的 $\min(a_1)+\min(a_1,a_2)+\ldots+\min(a_1,a_2,\ldots,a_n)$ 的最小值。

说明/提示

在第二个测试用例中，在 $i=2,j=3$ 时操作可以得到最优解。

在第三个测试用例中，不操作即为最优解。

样例

3
2
1 2
3
1 2 3
4
3 0 2 3

2
2
3