[1] Using dynamic programming

Let us call an integer sequence where the absolute difference between adjacent elements is always \(1\) (including a length-\(1\) sequence) a fantastic IS.

Consider the following dynamic programming:

\(\mathrm{dp}[i][j][k]:=(\)the number of ways to make a sequence of fantastic ISs \(C_1,C_2,\dots,C_j\) by only using values at most \(i\) while satisfying all of the following conditions\()\)

• For each $l$ such that $2 \le l \le j$, $C_l$ begins with $i$.
• For each $l$ such that $1 \le l \le j-1$, $C_l$ ends with $i$.
• Exactly $k$ of the beginning of $C_1$ and the end of $C_j$ is less than or equal to $i-1$.

This counts the number of sequences of arrays that can result when only extracting values at most \(i\) from \(B\). For example, the fantastic IS \((2,3,2,1,2,3,4,3,4,3,2,3)\) goes through the following four entries of the table \(\mathrm{dp}\).

• $(1)$ $(\mathrm{dp}[1][1][0])$
• $(2),(2,1,2),(2)$ $(\mathrm{dp}[2][3][0])$
• $(2,3,2,1,2,3),(3),(3,2,3)$ $(\mathrm{dp}[3][3][1])$
• $(2,3,2,1,2,3,4,3,4,3,2,3)$ $(\mathrm{dp}[4][1][1])$

One can consider this process as insertions to perform the transitions in this dynamic programming. Summing up \(\mathrm{dp}[i][j][0],\mathrm{dp}[i][j][1],\mathrm{dp}[i][j][2]\) yields \(\mathrm{dp}[i+1]\).

\(\begin{cases} \mathrm{dp}[i+1][A_{i+1}-j][0] = \mathrm{dp}[i][j][0] \times \binom{A_{i+1}-1}{j} \\ \mathrm{dp}[i+1][A_{i+1}-j+1][1] = \mathrm{dp}[i][j][0] \times 2 \times \binom{A_{i+1}-1}{j-1} \\ \mathrm{dp}[i+1][A_{i+1}-j+2][0] = \mathrm{dp}[i][j][0] \times \binom{A_{i+1}-1}{j-2} \end{cases}\)

\(\begin{cases} \mathrm{dp}[i+1][A_{i+1}-j+1][1] = \mathrm{dp}[i][j][1] \times \binom{A_{i+1}-1}{j-1} \\ \mathrm{dp}[i+1][A_{i+1}-j+2][2] = \mathrm{dp}[i][j][1] \times \binom{A_{i+1}-1}{j-2} \end{cases}\)

\(\begin{cases} \mathrm{dp}[i+1][A_{i+1}-j+2][2] = \mathrm{dp}[i][j][2] \times \binom{A_{i+1}-1}{j-2} \end{cases}\)

---

[2] Complexity analysis

In the above dynamic programming, if we maintain all triples of \((i,j,k)\), the complexity will be \(\mathrm{O}(N \times \max A)\).

We will try to reduce the complexity by only maintaining \((i,j,k)\) where \(\mathrm{dp}[i][j][k] \neq 0\).

For a fixed \((i,k)\), let us examine the values of \(j\) such that \(\mathrm{dp}[i][j][k] \neq 0\). For simplicity, let \(X_i = A_i - A_{i-1} + A_{i-2} - A_{i-3} + \dots\).

\(\begin{array}{c|ccccc} & 0 & 1 & 2\\ \hline 1 & X_1 & & \\ \hline 2 & X_2 & X_2+1 & X_2+2 \\ \hline 3 & X_3 & X_3,X_3+1 & X_3,X_3+1,X_3+2 \\ \hline 4 & X_4 & X_4,X_4+1 & X_4,X_4+1,X_4+2 \end{array}\)

From this, one can see that the number of \((i,j,k)\) such that \(\mathrm{dp}[i][j][k] \neq 0\) is \(\mathrm{O}(N)\).

---

[3] Summary

The problem can therefore be solved in \(\mathrm{O}(N + \max A)\).

One can simplify the implementation by using associative arrays, for example.