Prepared by: Toni Brajko

Let's observe the part of the sequence that is strictly positive. Notice that it will form a continuous segment, so we can disregard the zeroes before and after it. Denote ~ans_i~ as the number of ways to form a sequence of length ~i~ (without zeroes). To account in the zeroes, we see that we can place a sequence of length ~i~ on ~k-i+1~ ways (~i \le k~) in the initial sequence. Therefore, the solution is given with the following expression:

$$\displaystyle \sum_{i=1}^{\min(n,k)} ans_i \cdot (k-i+1)$$

It remains to calculate ~ans_i~ for each ~i~.

We can generate every possible sequence of moves and use it to calculate the final sequence we get. To count the number of different sequences, we can, for example, sort them (and then if two sequences are equal they will necessarily be neighboring). The complexity of this algorithm is ~\mathcal O(n^2 \cdot n^2)~ or ~\mathcal O(n \cdot 2^n)~, depending on the implementation, and is sufficient to solve the first subtask.

Let's observe creating the sequence backwards. We have ~(n)~ as the initial sequence. For each number from ~n-1~ to ~1~ in decreasing order, we put number ~i~ next to ~i+1~. If we put a number on an already existing position, the sequence won't change (because the larger number will come after in the original process, and it will "overwrite" the lower one). If we want to put a number on a place where we haven't written any numbers yet (i.e. on a zero, which is not included in current sequence because we disregarded it), the sequence will extend by one spot either to the left or to the right. Notice that this process is equivalent to the original one.

We use dynamic programming to solve the rest of the task. Let ~dp[i][j]~ be the number of achievable sequences of length ~i~, such that ~j~ is the minimum of the sequence. Notice that the minimum of any such sequence will be one of its endpoints. This follows directly from the aforementioned description. WLOG, assume the smallest element in the sequence is the right endpoint. We have two possibilities:

• The second smallest element of the sequence is also on the right end, one place to the left from the smallest element. It can be any number of the form ~j-1-2k~, for ~k \in \mathbb N~.
• The second smallest element of the sequence is the left endpoint. It can be any number of the form ~j+i-1+2k~, for ~k \in \mathbb N^0~.

Detailed analysis of these expressions is left as an exercise for the reader. Now the following holds:

$$\displaystyle dp[i][j] = \sum_{k=1}^{\left\lfloor \frac{n-j+1}{2} \right\rfloor} dp[i-1][j-1+2k] + \sum_{k=0}^{\left\lfloor \frac{n-j-i+1}{2} \right\rfloor} dp[i-1][j+i-1+2k]$$

$$\displaystyle ans_i = \sum_{j=1}^n dp[i][j]$$

The complexity of each transition is ~\mathcal O(n)~, and there are a total of ~\mathcal O(n^2)~ states, so the final complexity of direct implementation of this formula is ~\mathcal O(n^3)~, and is sufficient to solve the second and the third subtask.

Finally, we can speed up each transition by using prefix sums by parity, since the independent term is always ~2k~. Final complexity is ~\mathcal O(n^2)~. Notice that it does not depend on the sequence length ~k~ from the task statement at all. For details of implementation and base cases refer to the official solution.