当前没有测试数据。

题目背景

Y 同学作为一名顶尖的🧄法优化专家，正在分析一个复杂的资源调度流程。该流程由 $N$ 个连续的阶段组成，每个阶段都有一个初始成本。Y 同学发现，他有一次宝贵的机会，可以将某个后续阶段的成本完全转移到一个较早的阶段上。他希望利用这次机会，使得整个流程的“累计最低成本”之和达到最小。

题目描述

给定一个长度为 $N$ 的整数序列 $A = (A_1, A_2, \dots, A_N)$。

你最多可以执行一次以下操作：

• 选择两个下标 $i, j$ 满足 $1 \le i < j \le N$。
• 将 $A_j$ 的值加到 $A_i$ 上，然后将 $A_j$ 的值置为 $0$。即，令 $A_i \leftarrow A_i + A_j$，$A_j \leftarrow 0$。

你需要决定是否执行这次操作，以及如果执行，选择哪一对 $(i, j)$，以使得最终序列的前缀最小值之和最小。

前缀最小值之和定义为：

本题包含多组测试用例。

输入格式

第一行包含一个整数 $T$，表示测试用-例-的-数-量。

对于每组测试用例： 第一行包含一个整数 $N$。 第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$。

输出格式

对于每组测试用例，输出一行一个整数，表示可能的最小前缀最小值之和。

样例

样例输入 #1

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

样例输出 #1

2
2
3

提示

数据范围与约定

• $1 \le T \le 10^4$
• $2 \le N \le 2 \cdot 10^5$
• $0 \le A_i \le N$
• 所有测试用例的 $N$ 的总和不超过 $2 \cdot 10^5$。