Given a list of elements, you can remove either left or right element and add this to a new list either as first element or last element. You have to do this to form a new list such that inversions are minimized. (inversion means l [i] > l [j] for i<j). How to approach this problem efficiently?
Maintain a DP on the array segments :
DP[i][j] = Best you can do when sub-array A(i..j) is still in the old line.
Notice that we can place A[i]/A[j] in the beginning/end of the new line.
Thus, we must consider all these cases in our DP.
[DP(i)(j) = min(DP[i + 1][j] + min(a, b), DP[i][j — 1] + min(c, d)) ]
Where,
a = number of elements lesser than A[i] in [0..i-1] U [j+1..N-1]
b = number of elements greater than A[i] in [0..i-1] U [j+1..N-1]
c = number of elements lesser than A[j] in [0..i-1] U [j+1..N-1]
d = number of elements greater than A[j] in [0..i-1] U [j+1..N-1]
Implementing this would result in complexity, but we can easily optimize this to by pre-computing some stuff for each index.