For convenience, let \(A_0=0,A_{N+1}=N+1\) and we will count subsequences containing \(A_0\) and \(A_{N+1}\).

Assume that, for \(0 = x_0 <x_1< \cdots < x_k < x_{k+1}=N+1\), there is a unique way to extract the subsequence \(s=(A_{x_0},A_{x_1},\cdots,A_{x_{k+1}})\).

Then, it is necessary that the following holds for each \(0 \leq i \leq k\):

• None of \(A_{x_i+1},A_{x_i+2},\cdots,A_{x_{i+1}-1}\) equals \(A_{x_i}\) or \(A_{x_{i+1}}\).

Otherwise, there would be another way to extract the same subsequence.

On the other hand, when the above condition is satisfied, the extraction of \(s\) is unique. We can show this from the fact that the greedy extraction of \(s\) from the beginning of \(A\) (making the used indices lexicographically smallest) will coincide with the greedy extraction of \(s\) from the end of \(A\) (making the used indices lexicographically largest).

Thus, we can find the answer by counting the sequences of indices \(x\) satisfying the condition above. We can implement it with Binary Indexed Tree to achieve the time complexity of \(O(N \log N)\).