codeforces#P1984C2. Magnitude (Hard Version)
Magnitude (Hard Version)
Description
The two versions of the problem are different. You may want to read both versions. You can make hacks only if both versions are solved.
You are given an array $a$ of length $n$. Start with $c = 0$. Then, for each $i$ from $1$ to $n$ (in increasing order) do exactly one of the following:
- Option $1$: set $c$ to $c + a_i$.
- Option $2$: set $c$ to $|c + a_i|$, where $|x|$ is the absolute value of $x$.
Let the maximum final value of $c$ after the procedure described above be equal to $k$. Find the number of unique procedures that result in $c = k$. Two procedures are different if at any index $i$, one procedure chose option $1$ and another chose option $2$, even if the value of $c$ is equal for both procedures after that turn.
Since the answer may be large, output it modulo $998\,244\,353$.
The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.
The first line of each test case contains a single integer $n$ ($2 \leq n \leq 2 \cdot 10^5$).
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 sum of $n$ over all test cases does not exceed $3 \cdot 10^5$.
For each test case, output a single integer — the number of unique procedures that result in $c = k$, modulo $998\,244\,353$.
Input
The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.
The first line of each test case contains a single integer $n$ ($2 \leq n \leq 2 \cdot 10^5$).
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 sum of $n$ over all test cases does not exceed $3 \cdot 10^5$.
Output
For each test case, output a single integer — the number of unique procedures that result in $c = k$, modulo $998\,244\,353$.
5
4
2 -5 3 -3
8
1 4 3 4 1 4 3 4
3
-1 -2 -3
4
-1000000000 1000000000 1000000000 1000000000
4
1 9 8 4
12
256
1
8
16
Note
In the first test case, it can be shown that our maximal final value of $c$ is $3$. There are $12$ ways to achieve this because in order to get $3$, we have to take absolute value at indices $2$ or $4$, or both, resulting in $3$ ways. For the other two indices, it doesn't change the value whether we take absolute value or not, so we have $2 \cdot 2 = 4$ ways for them. In total, we have $3 \cdot 4 = 12$ ways.
In the second test case, taking the absolute value will never change anything, so we can either take absolute value or not, for every index. This gives us $2^8 = 256$ possible ways.