该问题与问题 G 不同。在该问题中,您必须输出 最小值 最多一次操作后的前缀最小值之和。
给定一个长度为 $$$n$$$ 的数组 $$$a$$$,其元素满足 $$$\boldsymbol{0 \le a_i \le n}$$$。您可以执行以下操作 最多一次:
- 选择两个索引 $$$i$$$ 和 $$$j$$$ 使得 $$$i \lt 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 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 2\cdot 10^5$$$) — $$$a$$$ 的长度。
以下行包含 $$$n$$$ 以空格分隔的整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n$$$) — 表示数组 $$$a$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。
输出
对于每个测试用例,在新行中输出一个整数,即 $$$\min(a_1) + \min(a_1,a_2) + \ldots + \min(a_1, a_2, \ldots, a_n)$$$ 的最小可能值。
示例
输入复制
321 231 2 343 0 2 3
输出复制
2 2 3
注意
在第二个测试用例中,最好使用 $$$i=2$$$ 和 $$$j=3$$$ 执行操作。
在第三个测试用例中,最好不执行任何操作。答案是$$$3$$$。