I currently have a problem, whose solution requires to remove from a permutation of $\lbrace 1,\ \dots,\ n\rbrace$ those values that are to the left of a smaller one.


My idea was to remove the complement of the [longest increasing subsequence](https://en.wikipedia.org/wiki/Longest_increasing_subsequence), but am not quite sure, if that yields the correct result (which I doubt, because the longest increasing subsequence need not be unique, whereas the inversion relation is) and/or whether it would be the most efficient way to remove all inversions.



> 
> **Questions:**
> 
> 
> * does the longest increasing subsequence of a permutation represent the complement of all inversions?
> * what is the fastest known algorithm for removing all "inverted" elements from a permutation?
> 
> 
> 



Algorithm for Removing Inverted Elements from a Permutation
Create a doubly-linked list $L$, initially empty. Scan a given permutation $p=(p\_1,p\_2,\dots,p\_n)$ from left to right, and for each element $p\_i$ perform the following operations:


1. (loop) While $L$ is not empty and $p\_i$ is smaller than the last element of $L$, remove this last element from $L$.
2. Append $p\_i$ to $L$.


At the end, $L$ will contain a required subpermutation of $p$. Notice that visiting (i.e., comparison to) every element of $L$ results in either appending or removal of an element to/from $L$. The total number of such operations does not exceed $2n$, since every element of $p$ may be appended to $L$ only once and removed from $L$ only once. So, this is a linear-time algorithm.


