CF2053I2.Affectionate Arrays (Hard Version)

Note that this statement is different to the version used in the official round. The statement has been corrected to a solvable version. In the official round, all submissions to this problem have been removed.

This is the hard version of the problem. The difference between the versions is that in this version, you need to compute the sum of value of different 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!

For a possible array $b_1, b_2, \ldots, b_m$ satisfying all the conditions above, Victor defines the value of the array as the number of occurrences of array $a$ as subsequences in array $b$. That is, he counts the number of array $c_1, c_2, \ldots, c_{n}$ that $1\le c_1 \lt c_2 \lt \ldots \lt c_n\le m$ and for all integer $i$ that $1\le i\le n$, $b_{c_{i}}=a_i$ is satisfied, and let this be the value of array $b$.

Even constrained as above, there are still too many possible gifts. So Victor asks you to calculate the sum of value of all possible arrays $b_1, b_2, \ldots, b_m$. Since the answer may be large, Victor only needs the number modulo $998\,244\,353$. He promises you: if you help him successfully, he will share a bit of Iris's birthday cake with you.

$^{\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.

注意：本题面与正式比赛轮次中使用的版本不同。题面已修正为可解版本。在正式比赛轮次中，本题的所有提交均已被移除。

本题是该问题的困难版本。两个版本的区别在于：在本版本中，你需要计算所有满足条件的不同数组 $b$ 的“价值”之和。仅当你已解决该问题的所有版本时，才允许你进行 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 将能尽快领会他的心意！

对于任意一个满足上述全部条件的可能数组 $b_1, b_2, \ldots, b_m$，Victor 将该数组的“价值”定义为：数组 $a$ 作为子序列在数组 $b$ 中出现的次数。即，统计满足如下条件的数组 $c_1, c_2, \ldots, c_{n}$ 的个数：
$1\le c_1 \lt c_2 \lt \ldots \lt c_n\le m$，且对所有整数 $i$（$1\le i\le n$），均有 $b_{c_{i}}=a_i$。该计数值即为数组 $b$ 的价值。

即使在上述约束下，仍存在太多可能的礼物。因此 Victor 请求你计算所有可能的数组 $b_1, b_2, \ldots, b_m$ 的价值之和。由于答案可能很大，Victor 只需要结果对 $998\,244\,353$ 取模后的值。他向你保证：只要你成功帮他完成此任务，他将分你一小块 Iris 的生日蛋糕。

$^{\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 sum of values of valid arrays $b_1, b_2, \ldots, b_m$, modulo $998\,244\,353$.

对于每个测试用例，输出一行，包含一个整数：所有合法数组 $b_1, b_2, \ldots, b_m$ 的值之和，对 $998\,244\,353$ 取模。

In the first test case, $a=[1, 2, 3, 4]$. The only possible array $b$ is $[1, 2, 3, 4]$, and its value is $1$.

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]$. Both arrays have value $1$.

In the third test case, $a=[1, -2, 2, 1]$. The only possible array $b$ is $[1, 1, -2, 2, -1, 1]$. It has value $2$, because we can find arrays $c=[1,3,4,6]$ or $[2,3,4,6]$. That is, the array $a$ occurs twice in $b$, so the answer is $2$.

在第一个测试用例中，$a=[1, 2, 3, 4]$。唯一可能的数组 $b$ 是 $[1, 2, 3, 4]$，其值为 $1$。

在第二个测试用例中，$a=[2, -3, 2, 2]$。可能的数组 $b$ 有 $[1, 2, -3, 2, -1, 2]$ 和 $[2, 1, -3, 2, -1, 2]$。这两个数组的值均为 $1$。

在第三个测试用例中，$a=[1, -2, 2, 1]$。唯一可能的数组 $b$ 是 $[1, 1, -2, 2, -1, 1]$。它的值为 $2$，因为我们能找到数组 $c=[1,3,4,6]$ 或 $[2,3,4,6]$。也就是说，数组 $a$ 在 $b$ 中出现了两次，因此答案为 $2$。