P8848 [JRKSJ R5] 1-1 B

This problem is a harder version of 1-1. The easier version is [1-1 A](https://www.luogu.com.cn/problem/P8847).

You are given a sequence $a$. For all $i \in [1,n]$, $a_i \in \{1,-1\}$. You need to count how many sequences obtained by rearranging $a$ make the maximum subarray sum as small as possible. Two sequences are considered different if and only if there exists at least one position where the numbers are different.

The first line contains an integer $n$. The second line contains $n$ integers representing $a$.

Output one integer representing the answer. The answer should be taken modulo $998244353$.

Definition of the maximum subarray sum: the maximum value of the sum over any interval in the sequence, i.e., $\max_{1\le l\le r\le n} \sum_{i=l}^r a_i$. ### Constraints This problem uses bundled testdata. | $\text{Subtask}$ | $n\le$ | $\text{Score}$ | | :----------: | :----------: | :----------: | | $1$ | $10$ | $20$ | | $2$ | $100$ | $20$ | | $3$ | $500$ | $20$ | | $4$ | $10^4$ | $40$ | For $100\%$ of the testdata, $1\le n\le 10^4$, $a_i\in \{1,-1\}$. # Input Format # Output Format Translated by ChatGPT 5