CF1517E.Group Photo

In the 2050 Conference, some people from the competitive programming community meet together and are going to take a photo. The $n$ people form a line. They are numbered from $1$ to $n$ from left to right. Each of them either holds a cardboard with the letter 'C' or a cardboard with the letter 'P'.

Let $C={c_1,c_2,\dots,c_m}$ $(c_1 \lt c_2 \lt \ldots \lt c_m)$ be the set of people who hold cardboards of 'C'. Let $P={p_1,p_2,\dots,p_k}$ $(p_1 \lt p_2 \lt \ldots \lt p_k)$ be the set of people who hold cardboards of 'P'. The photo is good if and only if it satisfies the following constraints:

1. $C\cup P={1,2,\dots,n}$
2. $C\cap P =\emptyset $.
3. $c_i-c_{i-1}\leq c_{i+1}-c_i(1 \lt i \lt m)$.
4. $p_i-p_{i-1}\geq p_{i+1}-p_i(1 \lt i \lt k)$.

Given an array $a_1,\ldots, a_n$, please find the number of good photos satisfying the following condition: $$\sum\limits_{x\in C} a_x \lt \sum\limits_{y\in P} a_y.$$

The answer can be large, so output it modulo $998\,244\,353$. Two photos are different if and only if there exists at least one person who holds a cardboard of 'C' in one photo but holds a cardboard of 'P' in the other.

在 2050 大会中，来自竞技编程社区的一些人相聚一堂并准备合影。这 $n$ 个人排成一列，从左到右依次编号为 $1$ 到 $n$。每个人手中要么持有一张写有字母 'C' 的纸板，要么持有一张写有字母 'P' 的纸板。

令 $C = \{c_1, c_2, \dots, c_m\}$（其中 $c_1 < c_2 < \ldots < c_m$）表示手持 'C' 纸板的人的编号集合；令 $P = \{p_1, p_2, \dots, p_k\}$（其中 $p_1 < p_2 < \ldots < p_k$）表示手持 'P' 纸板的人的编号集合。当且仅当满足以下约束时，该合影被称为“好的”：

1. $C \cup P = \{1, 2, \dots, n\}$；
2. $C \cap P = \emptyset$；
3. $c_i - c_{i-1} \leq c_{i+1} - c_i$（对所有 $1 < i < m$ 成立）；
4. $p_i - p_{i-1} \geq p_{i+1} - p_i$（对所有 $1 < i < k$ 成立）。

给定一个数组 $a_1, \ldots, a_n$，请计算满足如下条件的“好的”合影数量：

$$\sum\limits_{x\in C} a_x < \sum\limits_{y\in P} a_y.$$

答案可能很大，请对 $998\,244\,353$ 取模后输出。当且仅当存在至少一个人，在一张合影中持 'C' 纸板、而在另一张合影中持 'P' 纸板时，这两张合影被视为不同。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 200\,000$). Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1\leq n\leq 200\,000$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $200\,000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 200\,000$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1\leq n\leq 200\,000$）。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$）。

保证所有测试用例的 $n$ 之和不超过 $200\,000$。

For each test case, output the answer modulo $998\,244\,353$ in a separate line.

对于每个测试用例，在单独一行中输出对 $998\,244\,353$ 取模后的答案。

For the first test case, there are $10$ possible good photos satisfying the condition: PPPPP, CPPPP, PCPPP, CCPPP, PCCPP, PCPCP, PPPPC, CPPPC, PCPPC, PPPCC.

For the second test case, there are $7$ possible good photos satisfying the condition: PPPP, PCPP, PCCP, PPPC, PCPC, PPCC, PCCC.

对于第一个测试用例，共有 $10$ 种满足条件的“好照片”：PPPPP、CPPPP、PCPPP、CCPPP、PCCPP、PCPCP、PPPPC、CPPPC、PCPPC、PPPCC。

对于第二个测试用例，共有 $7$ 种满足条件的“好照片”：PPPP、PCPP、PCCP、PPPC、PCPC、PPCC、PCCC。