E. Group Phototime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputIn 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<c_2<\ldots <c_m) be the set of people who hold cardboards of 'C'. Let P=\{p_1,p_2,\dots,p_k\} (p_1<p_2<\ldots <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:   C\cup P=\{1,2,\dots,n\}  C\cap P =\emptyset .  c_i-c_{i-1}\leq c_{i+1}-c_i(1< i <m).  p_i-p_{i-1}\geq p_{i+1}-p_i(1< i <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 < \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.InputEach 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.OutputFor each test case, output the answer modulo 998\,244\,353 in a separate line.ExampleInput
3
5
2 1 2 1 1
4
9 2 2 2
1
998244353
Output
10
7
1
NoteFor 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.
3
5
2 1 2 1 1
4
9 2 2 2
1
998244353

10 7 1 
['binary search', 'data structures', 'implementation', 'two pointers', '*2500']