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, 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?