Here is my approach
First I compute the longest non decreasing sub-sequence in $N \log N$ time. Algorithm to do this (that only uses arrays and binary search) can be found here: http://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms
Let's suppose the longest subsequence has $L$ elements. Then if $L < N - M$, there isn't any way to solve the problem since there's no subsequence of length $N - M$ that's still sorted.
Otherwise, just remove the $N - L$ elements that aren't in the subsequence, and then remove more at random until exactly M total have been removed. In all this is an $N \log N$ algorithm.
I want to know, is there any more efficient algorithm (i.e. $O( N)$ ) to solve this problem ?