At first, observe that the definition of mean sequence can be applied to any sequence, not only nondecreasing sequences. If we drop the condition that sequence ~s_1, \dots, s_{n+1}~ is nondecreasing, then fixing a single ~s_i~ fixes the entire sequence, given its mean sequence ~m_1, \dots, m_n~. Let us define the reflection operation ~r~ on integer ~a~ with respect to center ~c~ as follows: ~r(a,c) = b~ if and only if ~\frac{a+b}{2} = c~; that is, ~r(a,c) = 2c-a~. If ~s_i~ is fixed, then ~s_{i+1} = r(s_i,m_i)~ and ~s_{i-1} = r(s_i,m_{i-1})~, etc. Hence, there exist an infinite number of sequences ~s_1, \dots, s_{n+1}~ that have the given sequence ~m_1, \dots, m_n~ as mean sequence — one for each choice of ~s_1~.

There is a finite number of nondecreasing sequences though. A simple upper bound on the number of possible nondecreasing sequences may be ~m_2-m_1+1~, which is the number of integers between ~m_1~ and ~m_2~ (inclusive). This is because ~s_2~ must satisfy ~m_1 \le s_2 \le m_2~. Indeed, if ~s_2 < m_1~ then ~s_1 > m_2~ and therefore ~s_2 < s_1~ so the sequence is not nondecreasing. Similarly, if ~s_2 > m_2~ then ~s_3 < m_2~ gives a sequence which is not nondecreasing either. This way we can construct a solution, which tests all the possible values of ~s_2~ lying between ~m_1~ and ~m_2~, and for each such ~s_2~ it computes the rest of the sequence and then checks if it is nondecreasing. Such a solution works in ~\mathcal O(n(m_2-m_1+1))~ time and can be implemented with ~\mathcal O(n)~ or better ~\mathcal O(m_2-m_1+1)~ memory complexity.

Optimal solution

Before we present the model solution, the following definition will be useful. Let us call a value ~v~ feasible for ~s_i~ in the given sequence, when there exists a nondecreasing sequence ~s_1, \dots, s_{n+1}~ with ~s_i = v~ and mean sequence ~m_1, \dots, m_n~. Now we need an important observation.

Observation 1 If, for some ~i~, values ~a~ and ~b~ with ~a \le b~ are feasible for ~s_i~, then every ~c~ in the interval ~[a,b]~ is feasible for ~s_i~.

The actual number of nondecreasing sequences ~s_1, \dots, s_{n+1}~ can be obtained by generalizing the problem as follows. Given a nondecreasing sequence ~m_1, \dots, m_n~, determine the interval of feasible values for ~s_{n+1}~. The answer is then the size of that interval.

In the model solution, the interval of feasible values of ~s_{n+1}~ is computed inductively. We start with the case ~n = 0~. In this case, the interval of feasible values for ~s_1~ consists of all integers: ~(-\infty,+\infty)~. Now let ~[a,b]~ be the interval for nondecreasing sequences ~s_1, \dots, s_{n+1}~ having mean sequence ~m_1, \dots, m_n~. Let us consider the mean sequence ~m_1, \dots, m_n~ extended by a new element ~m_{n+1} \ge m_n~. This reduces the possible values for ~s_{n+1}~ to the interval ~[a,\min(b,m_{n+1})]~, and hence the interval for ~s_{n+2}~ is the reflection of this interval, that is, ~[r(\min(b,m_{n+1}),m_{n+1}),r(a,m_{n+1})]~. We consider interval ~[a,b]~ as empty if ~a > b~, and otherwise it contains ~b-a+1~ elements. This way we obtain ~\mathcal O(n)~ time complexity and ~\mathcal O(1)~ memory complexity solution, because there is no need to store the entire sequence in memory. Intervals of feasible values can be computed while reading the input data.

There are also some suboptimal solutions, which use different methods of determining the interval of feasible values for ~s_{n+1}~. One idea would be to use binary search. Even though this can result in an algorithm with ~\mathcal O(n \log n)~ time complexity, it will need ~\mathcal O(n)~ memory, which is too much to pass the largest tests.