E. Групповое фото
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На конференции 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$$$ на новой строке.

Пример
Входные данные
3
5
2 1 2 1 1
4
9 2 2 2
1
998244353
Выходные данные
10
7
1
Примечание

В первом наборе входных данных есть $$$10$$$ хороших фото, которые удовлетворяют условию: PPPPP, CPPPP, PCPPP, CCPPP, PCCPP, PCPCP, PPPPC, CPPPC, PCPPC, PPPCC.

Во втором наборе входных данных есть $$$7$$$ хороших фото, которые удовлетворяют условию: PPPP, PCPP, PCCP, PPPC, PCPC, PPCC, PCCC