На конференции 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». Фото хорошее тогда и только тогда, когда выполнены следующие ограничения:
Вам дан массив $$$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
Название |
---|