Minimizing the Maximum Subarray Sum

You are given a sequence \(a\) of length \(n\) where each \(a_i\in\{1, -1\}\) for \(1\le i\le n\). You can rearrange (i.e. permute) the elements of \(a\) arbitrarily. Two sequences are considered different if there is at least one position where they differ.

Let the maximum subarray sum of a sequence be defined as \[ M(a)=\max_{1\le i\le j\le n}\sum_{k=i}^{j}a_k. \] Your task is to determine in how many ways you can rearrange the sequence \(a\) so that the resulting sequence has the minimum possible maximum subarray sum.

Observation: Suppose the given sequence contains \(p\) ones and \(q\) negative ones (\(-1\)). In any rearrangement, if we view the sequence as blocks of consecutive ones separated by the \(-1\)s, there will be \(q+1\) such blocks. To minimize the maximum subarray sum, you want to balance the ones as evenly as possible among these blocks. The optimal (minimal) possible maximum subarray sum is \[ L=\left\lceil \frac{p}{q+1} \right\rceil. \] In order for a rearrangement to achieve this, if we let \(x_1,x_2,\dots,x_{q+1}\) be the number of ones in each block (allowing zeros), then we must have:

• \(x_1+x_2+\cdots+x_{q+1}=p\),
• each \(0\le x_i\le L\), and
• at least one \(x_i\) must equal \(L\) (so that the maximum is exactly \(L\)).

The answer is the number of ways to choose nonnegative integers \(x_1,\dots,x_{q+1}\) satisfying the above conditions. Note that every valid distribution corresponds uniquely to one rearrangement of the sequence \(a\).

If \(p=0\) (i.e. all numbers are \(-1\)), then the only rearrangement produces a maximum subarray sum of \(0\), and the answer is \(1\).

inputFormat

The input consists of two lines. The first line contains a single integer \(n\) (the number of elements).

The second line contains \(n\) space-separated integers, each of which is either \(1\) or \(-1\).

outputFormat

Output a single integer: the number of rearrangements of \(a\) that yield the minimal possible maximum subarray sum.

sample

4
1 -1 1 -1

3