Problem Background

This problem is a more difficult version of 1-1, with an easier version available at 1-1 A.

1+1

Problem Description

Given a sequence \( a \) where \( \forall i \in [1, n], a_i \in \{1, -1\} \).

Determine how many permutations of \( a \) exist such that the maximum subarray sum of the sequence is minimized.

Two sequences are considered different if and only if they differ at any position.

Input Format

The first line contains an integer \( n \).

The second line contains \( n \) integers representing \( a \).

Output Format

Output a single integer representing the answer modulo \( 998244353 \).

Sample Input and Output

Sample Input #1

4
1 -1 1 -1

Sample Output #1

3

Sample Input #2

5
1 1 1 -1 1

Sample Output #2

3

Sample Input #3

10
1 1 1 1 1 1 1 -1 -1 -1

Sample Output #3

40

Notes

The definition of the maximum subarray sum is the maximum sum of any contiguous segment in the sequence, i.e., \( \max_{1 \le l \le r \le n} \sum_{i=l}^r a_i \).

Data Range

This problem uses batched testing.

For 100% of the data, \( 1 \le n \le 10^4 \) and \( a_i \in \{1, -1\} \).

见题面 Input 部分

见题面 Output 部分