Let’s first determine the general structure of such “LIS sequences” for permutations.

Consider any permutation \((P_1, P_2, \ldots, P_N)\). Let \(A_i\) be the length of the longest increasing subsequence of \((P_1, P_2, \ldots, P_{i-1}, P_{i+1}, P_N)\), and \(K\) be the length of the longest increasing subsequence of entire \(P\).

Clearly, \(K-1 \le A_i \le K\) for every \(i\). Also, it’s easy to see that \(A_i = K-1\) if and only if \(P_i\) appears in all longest increasing subsequences of \(P\), and \(A_i = K\) otherwise.

Let’s now consider any consecutive segment of \(K\)s (bounded by ends of the permutation or by \(K-1\)s). Let \(L\) be the element to the left end of this segment, or \(0\) if there isn’t any, and \(R\) be the element to the right of this segment, or \(N+1\) if there isn’t any. Clearly, no element from this segment that doesn’t lie in \([L+1, R-1]\) can ever be in any longest increasing subsequence of \(P\), so let’s consider only elements from this range. Denote them \(Q_1, Q_2, \ldots, Q_M\), and denote the length of the longest increasing subsequence of \(Q\) as \(K_1\).

It’s easy to see that \(K\) is equal to the number of \(i\) with \(A_i = K-1\), plus the sum of \(K_1\) over all these segments. Indeed, we have to take all \(i\) with \(A_i = K-1\) to every \(LIS\), and the maximum number of elements that we can fit “in between” two such adjacent \(K-1\)s (or ends) is precisely the corresponding \(K_1\).

Now, for a given \(Q_1, Q_2, \ldots, Q_M\) with \(LIS\) \(K_1\) (this is a different \(M\) from the \(M\) in the statement) , let \(f(i)\) denote the length of the longest increasing subsequence of \(Q\) ending at position \(i\). Clearly, \(1 \le f(i) \le K_1\) for each \(i\), and all integers from \(1\) to \(K_1\) appear. That means that if \(K_1>\frac{M}{2}\), then some number will appear exactly once as \(f(i)\). But this would mean that it has to be present in all longest increasing subsequences of \(Q\), and therefore in all longest increasing subsequences of \(P\) as well, which is impossible by choice. So, we must have \(K_1\le \frac{M}{2}\).

Firstly, let’s deal with the case when all elements of \(A\) are equal now. There are two cases: all of them are \(K-1\), or all are \(K\). If all are \(K-1\), it means that there all of them have to be in all longest increasing subsequences, so \(K = N\), and \(A = [N-1, N-1, \ldots, N-1]\). Clearly, this array works with permutation \((1, 2, 3, \ldots, N)\).

Otherwise, all of them are \(K\), which means that no element appears in all longest increasing subsequences, which implies \(K \le \frac{N}{2}\). For such \(K\), it’s not hard to construct the corresponding permutation: \((N-K+1, N-K+2, \ldots, N, N-2K+1, N-2K+2, \ldots, N-K, N-2K, N-2K-1, \ldots, 1)\). It’s easy to see that its \(LIS\) has length precisely \(K\), and that it has two disjoint \(LIS\)es.

Now, we suppose that both \(K-1\) and \(K\) are present. Then, the criteria above imply the following:

• $K$ has to be at least the number of $K-1$s.
• $K$ can't exceed the number of $K-1$s $+$ sum of $\lfloor \frac{M}{2} \rfloor$ over all consecutive segments $Q_1, Q_2, \ldots, Q_M$ of $K$s.

Let’s show that if these conditions hold, and if \(K\ge 3\) (as \(A_i \ge 2\)), then there exists a permutation \(P\) with given “LIS sequence” \(A\).

Let’s assign each consecutive segment of \(K\)s of length \(M\) (this is still a different \(M\) from the \(M\) in the statement) a number between \(0\) and \(\lfloor \frac{M}{2} \rfloor\), so that the number of \(K-1\)s \(+\) the sum of these numbers would be exactly \(K\). Let’s first deal with assigning elements to segments that got \(0\)s.

Suppose that segment \(P[L:R]\) got assigned zero. If the number of \(K-1\)s plus the sum of assigned numbers to the left of it is at least \(2\), we will call it a right segment, otherwise, we will call it left segment, and, clearly, the number of \(K-1\)s plus the sum of assigned numbers to the right of it is at least \(2\).

If the total length of the right segments is \(R_{total}\), fill them in one by one with numbers \(R_{total}, R_{total}-1, R_{total}-2, \ldots, 2, 1\). If the total length of the left segments is \(L_{total}\), fill them in one by one with numbers \(N, N-1, N-2, \ldots, N-L_{total}+1\).

Now let’s fill in the remaining positions, we will fill them with the remaining numbers one by one in the following way: if the current position is \(i\) with \(A_i = K-1\), we will just give it the smallest unused integer, if we are filling in a segment of length \(M\), which got assigned a positive number, say \(K_1\), we will fill corresponding elements of the permutation with next \(M\) free integers with the pattern above: \((M-K_1+1, M-K_1+2, \ldots, M, M-2K_1+1, M-2K_1+2, \ldots, M-K_1, M-2K_1, M-2K_1-1, \ldots, 1)\) (with some constant added to all of these).

This may have been hard to grasp, so let’s have an example. Suppose that \(A = [4, 5, 5, 5, 4, 5, 5, 5, 5, 5, 4, 5, 5]\). Then \(K = 5\) and we have \(3\) \((K-1)\)s, so we need to distribute \(2\) between \(3\) segments of \(K\)s. Let’s assign \(0\) to the first segment, \(2\) to the middle, and \(0\) again to the last one. Then the first segment is left segment, and the last one is right, which means that for now, we have filled in \([?, 13, 12, 11, ?, ?, ?, ?, ?, ?, ?, 2, 1]\). Now, let’s fill in the remaining elements, note that the middle segment of length \(5\) will have the form \([4, 5, 2, 3, 1]\) with some constant added to it. So, we get \([3, 13, 12, 11, 4, 8, 9, 6, 7, 5, 10, 2, 1]\).

Now, it’s not very hard to see that this permutation works. It clearly has an increasing subsequence of length \(K\). Note that no increasing subsequence can contain more than “assigned” \(K_1\) number of elements from any segment of \(K\)s (if \(K_1>0\)). Note also that the numbers in the left and right segments are going in decreasing order, so we can’t have more than \(1\) of those.

Suppose that some longest increasing subsequence of \(P\) contains an element from the left segments, say \(P_j\). Then, this subsequence can’t contain any elements to the right of \(P_j\), by our construction, as \(P_j\) is bigger than all of them. On the other side, the number of \(K-1\)s + the sum of \(K_1\)s to the left of \(P_j\) doesn’t exceed \(K-2\), so the total length of the subsequence can’t exceed \(K-1\), a contradiction. Similarly, no longest increasing subsequence of \(P\) contains an element from the right segments, so we just forget about all of them.

As for the remaining elements, there are some of them (precisely — elements at positions \(i\) with \(A_i = K-1\)) which are both prefix maximums and suffix minimums, so they will definitely be in every longest increasing subsequence, and for every other element, there is a longest increasing subsequence which doesn’t contain it. So, we proved that there exists a permutation \(P\) with given “LIS sequence” \(A\).

But that’s only part of the problem, now we need to count the number of arrays that satisfy the criteria. First, we count the number of arrays with all \(A_i\) equal, that’s easy to do. Now, let’s suppose that an array contains \(X\) \(K-1\)s, and that the sum of \(\frac{M}{2}\) over the continuous segments of \(K\)s is \(Y\). Clearly, the number of those segments with odd length is precisely \(N - X - 2Y\) then. Let’s iterate over all such pairs of \(X, Y\), for which \(0 \le N-X-2Y \le X+1\). For each such pair and a fixed \(K\), there are \(\binom{X+1}{N-X-2Y}\) ways to choose which of \(X+1\) segments will have odd length, and then we would have to distribute \(Y\) blocks of \(K\)s of length \(2\) between \(X+1\) segments, and there are precisely \(\binom{X+Y}{X}\) ways to do so. Eventually, \(K\) will be valid only if \(X \le K \le X+Y\), so we will have to add \(\binom{X+1}{N-X-2Y} \cdot \binom{X+Y}{X} \cdot max(0, min(M, X+Y) - max(2, X)+1)\) to the answer.

Total complexity is \(O(N^2)\).

Bonus: Solve the problem in \(O(N)\).