Background

This problem is a harder version of 1-1. The easier version is 1-1 A.

Problem Description

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.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers representing $a$.

Output Format

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

4
1 -1 1 -1

3

5
1 1 1 -1 1

3

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

40

Hint

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.

For $100\%$ of the testdata, $1\le n\le 10^4$, $a_i\in \{1,-1\}$.

Input Format

Output Format

Translated by ChatGPT 5