Define a final array as an array that can be made by applying $$$0$$$ or more operations described in the problem. For ease of discussion, we will consider the empty array $$$[]$$$ as a valid final array, but we will subtract $$$1$$$ later from our answer when needed.

Notice these observations in general for an index $$$idx$$$ and an array $$$A$$$. Define also two recurrence relations $$$P$$$ and $$$Q$$$.

$$$P(idx)$$$ stores the number of valid final arrays in which $$$A[idx]$$$ is an element. To find the value of $$$P(idx)$$$, let us work backwards from the index $$$idx-1$$$. Set the value of $$$i$$$ initially equal to $$$idx-1$$$. If there are no values between index $$$i$$$ and $$$idx$$$ inclusive that are less than $$$i$$$ and $$$idx$$$, we have two choices:

• If we keep $$$A[i]$$$, we can 'clone' all the arrays in which $$$A[i]$$$ is an element, and append $$$A[idx]$$$ to them. There are $$$P(i)$$$ such arrays.
• If we remove $$$A[i]$$$, we set $$$i \leftarrow i-1$$$ to consider the previous element.

We stop when there is an element between $$$i$$$ and $$$idx$$$, inclusive, that is less than $$$i$$$ and $$$idx$$$. Why? If there is such an element, we can't remove all elements between $$$i$$$ and $$$idx$$$, so we would only be overcounting previous results.

To efficiently execute this, we only need to stop at the element just before the first element that is smaller than $$$A[idx]$$$. The proof is left to the reader as an exercise.

Meanwhile, $$$Q(idx)$$$ stores the number of valid final arrays in which $$$A[idx]$$$ is not an element. For the first element less than $$$A[idx]$$$, say $$$m$$$, we can remove all elements to the right of it, that is, we can remove the subarray $$$A[m+1..idx]$$$ altogether. That means we can 'clone' all final arrays that are valid when considering the subarray $$$A[1..m]$$$, without appending anything to it. There are $$$P(m) + Q(m)$$$ such arrays if $$$m \neq 0$$$, and $$$P(m) + Q(m) - 1$$$ such arrays if $$$m = 0$$$ (because we consider the empty array as a valid final array, but the problem doesn't, we have to subtract $$$1$$$).

Thus, we have now formulated two formulas.

From the first point, we have

and from the second point, we have

where $$$n$$$ is the last index between $$$1$$$ and $$$x-1$$$ inclusive such that $$$A[n] < A[x]$$$.

The base case would be $$$P(0) = 1$$$ and $$$Q(0) = 0$$$. Our answer will be $$$P(N) + Q(N)$$$.

We can implement this approach with two one-dimensional bottom-up DP arrays, prefix sum, and a method for finding RMQ, such as a segment tree. The final time complexity is $$$O(N \log N)$$$.