Counting Valid Base Sequences

You are given a non‐decreasing sequence of n integers M₁, M₂, …, M_n. We want to count the number of non‐decreasing integer sequences S₁, S₂, …, S_n+1 such that their consecutive averages (defined by \(M_i = \frac{S_i + S_{i+1}}{2}\) for \(1 \le i \le n\)) equal the given sequence M. It is guaranteed that the given \(M\) sequence consists of integers so that the average of every two consecutive \(S\) elements is an integer.

A crucial observation is that once the first term \(S_1\) is chosen, the whole sequence is determined by the recurrence:

[ S_{i+1} = 2M_i - S_i, \quad 1 \le i \le n. ]

The non-decreasing property \(S_1 \le S_2 \le \cdots \le S_{n+1}\) can be rephrased using the fact that for each \(i\) with \(1 \le i \le n\), we have \[ S_i \le S_{i+1} \Longleftrightarrow S_i \le \frac{S_i + S_{i+1}}{2} = M_i. \]

Thus, for every \(i\) from 1 to \(n\), the condition is:

• If the expression of \(S_i\) in terms of \(S_1\) is \(S_i = S_1 + C_i\) (i.e. the coefficient of \(S_1\) is +1), then we require

\[ S_1 + C_i \le M_i \quad \Longrightarrow \quad S_1 \le M_i - C_i. \]

• If it is \(S_i = -S_1 + C_i\) (i.e. the coefficient is -1), then the condition \(S_i \le M_i\) becomes

\[ -S_1 + C_i \le M_i \quad \Longrightarrow \quad S_1 \ge C_i - M_i. \]

By iterating the recurrence from \(i=1\) to \(n\) (with \(S_1\) as a parameter), one can compute the constants \(C_i\) for each \(S_i\) (for \(1 \le i \le n\)). The answer is then the number of integers \(x = S_1\) satisfying all the derived linear inequalities. In other words, if the overall lower bound is \(L\) and the overall upper bound is \(R\), the answer is:

[ \max(0, R - L + 1). ]

Note: It is assumed that n ≥ 2 so that there are both lower and upper constraints on \(S_1\). (For \(n=1\) the answer might be infinite if no extra conditions are imposed.)

inputFormat

The input consists of two lines. The first line contains a single integer n (\(n \ge 2\)), the length of sequence M. The second line contains \(n\) space‐separated integers M₁, M₂, …, M_n in non-decreasing order.

outputFormat

Output a single integer – the number of valid sequences S whose consecutive averages equal the given sequence M and that are non-decreasing. If no valid sequence exists, output 0.

sample

3
1 2 3

2