CF2053I1.Affectionate Arrays (Easy Version)

You are the beginning of the letter, the development of a poem, and the end of a fairy tale.

— ilem, Pinky Promise

This is the easy version of the problem. The difference between the versions is that in this version, you need to compute the minimum length of the arrays. You can hack only if you solved all versions of this problem.

Iris treasures an integer array $a_1, a_2, \ldots, a_n$. She knows this array has an interesting property: the maximum absolute value of all elements is less than or equal to the sum of all elements, that is, $\max(\lvert a_i\rvert) \leq \sum a_i$.

Iris defines the boredom of an array as its maximum subarray$^{\text{∗}}$ sum.

Iris's birthday is coming, and Victor is going to send her another array $b_1, b_2, \ldots, b_m$ as a gift. For some seemingly obvious reasons, he decides the array $b_1, b_2, \ldots, b_m$ should have the following properties.

• $a_1, a_2, \ldots, a_n$ should be a subsequence$^{\text{†}}$ of $b_1, b_2, \ldots, b_m$.
• The two arrays have the same sum. That is, $\sum\limits_{i=1}^n a_i = \sum\limits_{i=1}^m b_i$.
• The boredom of $b_1, b_2, \ldots, b_m$ is the smallest possible.
• Among the arrays with the smallest boredom, the length of the array $b$ (i.e., $m$) is the smallest possible. And in this case, Iris will understand his regard as soon as possible!

Even constrained as above, there are still too many possible gifts. So Victor asks you to compute the value of $\boldsymbol{m}$ of any array $b_1, b_2, \ldots, b_m$ satisfying all the conditions above. He promises you: if you help him successfully, he will share a bit of Iris's birthday cake with you.

Note: since the input is large, you may need to optimize it for this problem.

For example, in C++, it is enough to use the following lines at the start of the main() function:

int main() {    std::ios::sync_with_stdio(false);    std::cin.tie(nullptr); std::cout.tie(nullptr);}

$^{\text{∗}}$An array $c$ is a subarray of an array $d$ if $c$ can be obtained from $d$ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

$^{\text{†}}$A sequence $c$ is a subsequence of a sequence $d$ if $c$ can be obtained from $d$ by the deletion of several (possibly, zero or all) element from arbitrary positions.

你是信件的开头，是诗歌的发展，也是童话的结尾。

— ilem，《粉红约定》（Pinky Promise）

本题为该问题的简单版本。两个版本的区别在于：在本版本中，你只需计算数组的最小可能长度。仅当你已解决该问题的所有版本时，才允许进行 Hack。

Iris 珍藏着一个整数数组 $a_1, a_2, \ldots, a_n$。她知道该数组具有一个有趣的性质：所有元素的最大绝对值不大于所有元素之和，即 $\max(\lvert a_i\rvert) \leq \sum a_i$。

Iris 将一个数组的无聊度（boredom）定义为它的最大子数组$^{\text{∗}}$和。

Iris 的生日即将到来，Victor 打算送她另一个数组 $b_1, b_2, \ldots, b_m$ 作为礼物。出于某些看似显而易见的原因，他决定数组 $b_1, b_2, \ldots, b_m$ 应满足以下性质：

• $a_1, a_2, \ldots, a_n$ 必须是 $b_1, b_2, \ldots, b_m$ 的一个子序列$^{\text{†}}$；
• 两数组的元素之和相等，即 $\sum\limits_{i=1}^n a_i = \sum\limits_{i=1}^m b_i$；
• 数组 $b_1, b_2, \ldots, b_m$ 的无聊度应尽可能小；
• 在所有无聊度最小的数组中，数组 $b$ 的长度（即 $m$）应尽可能小。此时，Iris 将能尽快领会他的心意！

即便受到上述限制，仍存在太多可能的礼物。因此 Victor 请求你计算任意一个满足上述全部条件的数组 $b_1, b_2, \ldots, b_m$ 对应的 $\boldsymbol{m}$ 值。他向你承诺：只要你成功帮他完成，他将与你分享一小块 Iris 的生日蛋糕。

注意：由于输入规模较大，你可能需要为此题优化输入输出效率。

例如，在 C++ 中，只需在 main() 函数开头加入以下几行即可：

int main() {    std::ios::sync_with_stdio(false);    std::cin.tie(nullptr); std::cout.tie(nullptr);}

$^{\text{∗}}$ 若数组 $c$ 可通过从数组 $d$ 的开头删除若干（可能为零或全部）元素、再从末尾删除若干（可能为零或全部）元素而得到，则称 $c$ 是 $d$ 的一个子数组（subarray）。

$^{\text{†}}$ 若序列 $c$ 可通过从序列 $d$ 的任意位置删除若干（可能为零或全部）元素而得到，则称 $c$ 是 $d$ 的一个子序列（subsequence）。

Each test contains multiple test cases. The first line of input contains an integer $t$ ($1 \leq t \leq 10^5$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 3\cdot 10^6$) — the length of the array $a_1, a_2, \ldots, a_n$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9 \leq a_i \leq 10^9$) — the initial array. It is guaranteed that $\max(\lvert a_i\rvert) \leq \sum a_i$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $3\cdot 10^6$.

每个测试包含多个测试用例。输入的第一行包含一个整数 $t$（$1 \leq t \leq 10^5$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 3\cdot 10^6$），表示数组 $a_1, a_2, \ldots, a_n$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-10^9 \leq a_i \leq 10^9$），表示初始数组。保证 $\max(\lvert a_i\rvert) \leq \sum a_i$。

保证所有测试用例的 $n$ 之和不超过 $3\cdot 10^6$。

For each test case, output a single line containing an integer: the length $m$ of a valid array $b$.

对于每个测试用例，输出一行，包含一个整数：有效数组 $b$ 的长度 $m$。

In the first test case, $a=[1, 2, 3, 4]$. The only array $b$ which satisfies all the properties above is $[1, 2, 3, 4]$, so we should output $4$.

In the second test case, $a=[2, -3, 2, 2]$. The possible arrays $b$ are $[1, 2, -3, 2, -1, 2]$ and $[2, 1, -3, 2, -1, 2]$, so we should output $6$.

在第一个测试用例中，$a=[1, 2, 3, 4]$。唯一满足上述所有性质的数组 $b$ 是 $[1, 2, 3, 4]$，因此应输出 $4$。

在第二个测试用例中，$a=[2, -3, 2, 2]$。可能的数组 $b$ 有 $[1, 2, -3, 2, -1, 2]$ 和 $[2, 1, -3, 2, -1, 2]$，因此应输出 $6$。