Let us decrease each value in \(A\) by \(1\).

Consider a graph with \(N+1\) vertices \(0,1,\cdots,N\) and an edge \(i \to A_i\) for each \(i\) such that \(A_i \geq 0\).

Then, a good sequence corresponds to a decomposition of the \(N+1\) vertices to some number of paths.

We can see a length-\(K\) decreasing subsequence of \(A\) as a set of \(K\) nested edges, or a combination of vertices \(L_1<L_2<\cdots<L_K<R_K<\cdots<R_1\) with edges \(R_i \to L_i\).

We will count the ways to embed such \(K\) edges in a path-decomposition of \((0, 1, \cdots, N)\). Let us consider the two parts of the graph separately: the \(K\) paths containing the \(K\) edges, and the remaining vertices. Then, we further divide the vertices in the \(K\) paths into two sets: the set \(A\) of vertices to the left of \(L_K\) (including \(L_K\)) and the set \(B\) of vertices to the right of \(L_K\). Each of \(A\) and \(B\) in itself should be decomposed into \(K\) paths. On the other hand, for a fixed path-decomposition of \(A\) and \(B\), the \(K\) edges connecting them are uniquely determined. (The starting point of the \(i\)-th path from the right in \(A\) corresponds to the ending point of the \(i\)-th path from the left in \(B\).)

Eventually, after fixing the sizes of \(A\) and \(B\), we can count the corresponding number of ways to have the \(K\) edges by multiplying the following values.

• The number of ways to choose the vertices for \(A\) and \(B\) from the \(N+1\) vertices.
• The number of ways to decompose \(A\) into \(K\) paths.
• The number of ways to decompose \(B\) into \(K\) paths.
• The number of path-decompositions of the vertices not in \(A\) or \(B\).

For the numbers of path-decompositions, we can define \(dp[i][j]=\) (the number of ways to decompose the graph with \(i\) vertices into \(j\) paths) to compute all necessary values in \(O(N^2)\).

The total complexity of this method is \(O(N^2)\).

Sample submission (c++)