# 2A: Permutasi Mandiri

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 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 element, we can't remove all elements between $i$ and $idx$, so we would only be overcounting previous results.

To efficiently execute this alogrithmically, 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 exercise.

- $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
$$
P(x) = \sum_{i = n}^{x-1}P(i),
$$

and from the second point, we have
$$
Q(x) = P(n) + Q(n) - (n==0),
$$

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 $P(1) = 1$. 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 segment tree. The final time complexity is $O(N \log N)$.