在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”纸板时,两张照片是不同的。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$。
输出
对于每个测试用例,在单独的行中输出对 $$$998\,244\,353$$$ 取模的答案。
示例
输入 #1
3 5 2 1 2 1 1 4 9 2 2 2 1 998244353
输出 #1
10 7 1
注意
对于第一个测试用例,有 $$$10$$$ 可能的好照片满足条件:PPPPPP、CPPPP、PCPPP、CCPPP、PCCPP、PCPCP、PPPPC、CPPPC、PCPPC、PPPCC。
对于第二个测试用例,有 $$$7$$$ 可能的好照片满足条件:PPPP、PCPP、PCCP、PPPC、PCPC、PPCC、PCCC。