Minimal operations to sort a sequence I have a sequence $A = a_1,a_2,...,a_n$. I can choose any element and increase or decrease it by one and a single increase or decrease counts as a single step. I want to make the array sorted in non decreasing in minimal numbers of steps.

I want to prove the following. Consider all unique numbers in the sequence A. Then the optimal answer will be one of the possible combinations of the unique numbers.

e.g If the array $A = 1, 5, 8, 1$. All unique values $S = {1, 5, 8}$. Then the optimal answer will be one of possible sorted combinations of length 4 where elements are taken from S 

1 1 1 1 => cost=(1-1)+(5-1)+(8-1)+(1-1)=11

1 5 5 5 => cost=(1-1)+(5-5)+(8-5)+(5-1)=7

5 5 5 8

1 5 8 8

etc.

That is, the optimal answer is the sorted sequence such that all values of the optimal answer are taken from the set S. This implies that we don't need to take intermediate values under consideration.
Let $B = b_1, b_2, \ldots, b_n$ be a minimum-cost sorted sequence derived from $A = a_1, a_2, \ldots, a_n$.  Note that $b_i \geq \min A$; otherwise the cost could be decreased by adding 1 to all $b_i$ that are less than $\min A$.

Suppose $B$ contains an element that is different from all the $a_i$'s.  Let the first such element be $b_j$.

Either $j=1$, or $b_j &gt; b_{j-1}$ because $B$ is nondecreasing and $b_j = b_{j-1}$ for $j&gt;1$ would mean that $b_j$ is not the first element of $B$ not in $A$.

Let $b_j, b_{j+1}, \ldots, b_k$ be the subsequence of $B$ such that all its elements are not in $A$ and either $b_{k+1}$ is in $A$ or $k=n$.  Every $b_i$ for $j \leq i \leq k$ is such that $b_i \neq a_i$.  In addition, $b_k &lt; b_{k+1}$ if $k &lt; n$ and $b_{j-1} &lt; b_j$ if $j&gt;1$.

If $b_i &gt; a_i$ happened more often than $b_i &lt; a_i$ in the subsequence, it would be possible to decrease the cost of $B$ by decreasing all the $b_i$ for $j \leq i \leq k$ by $1$ without violating the monotonicity constraint.  Hence this is not possible.  

Likewise, $b_i &lt; a_i$ cannot happen more often than $b_i &gt; a_i$ in the subsequence.  It must be that the $b_i$ such that $b_i &gt; a_i$ are equal in number to those for which $b_i &lt; a_i$.  Therefore moving the segment between $j$ and $k$ down so that $b_j = b_{j-1}$ if $j&gt;1$ or $b_1 = \min{A}$ if $j=1$ does not change the cost of $B$ and makes $b_j$ an element of $A$.

In conclusion, if there is a minimum-cost sorted $B$ with an element not in $A$, then there is also another minimum-cost sorted $B'$ that either has all its elements in $A$, or has its first element outside of $A$ later than $B$.  Since the latter case can only occur finitely many times, there is an optimal sorted $B$ whose elements are all in $A$.
Let $B = b_1, b_2, \ldots, b_n$ be a minimum-cost sorted sequence derived from $A = a_1, a_2, \ldots, a_n$.  Note that $b_i \geq \min A$; otherwise the cost could be decreased by adding 1 to all $b_i$ that are less than $\min A$.

Suppose $B$ contains an element that is different from all the $a_i$'s.  Let the first such element be $b_j$.

Either $j=1$, or $b_j &gt; b_{j-1}$ because $B$ is nondecreasing and $b_j = b_{j-1}$ for $j&gt;1$ would mean that $b_j$ is not the first element of $B$ not in $A$.

Let $b_j, b_{j+1}, \ldots, b_k$ be the subsequence of $B$ such that all its elements are not in $A$ and either $b_{k+1}$ is in $A$ or $k=n$.  Every $b_i$ for $j \leq i \leq k$ is such that $b_i \neq a_i$.  In addition, $b_k &lt; b_{k+1}$ if $k &lt; n$ and $b_{j-1} &lt; b_j$ if $j&gt;1$.

If $b_i &gt; a_i$ happened more often than $b_i &lt; a_i$ in the subsequence, it would be possible to decrease the cost of $B$ by decreasing all the $b_i$ for $j \leq i \leq k$ by $1$ without violating the monotonicity constraint.  Hence this is not possible.  

Likewise, $b_i &lt; a_i$ cannot happen more often than $b_i &gt; a_i$ in the subsequence.  It must be that the $b_i$ such that $b_i &gt; a_i$ are equal in number to those for which $b_i &lt; a_i$.  Therefore moving the segment between $j$ and $k$ down so that $b_j = b_{j-1}$ if $j&gt;1$ or $b_1 = \min{A}$ if $j=1$ does not change the cost of $B$ and makes $b_j$ an element of $A$.

In conclusion, if there is a minimum-cost sorted $B$ with an element not in $A$, then there is also another minimum-cost sorted $B'$ that either has all its elements in $A$, or has its first element outside of $A$ later than $B$.  Since the latter case can only occur finitely many times, there is an optimal sorted $B$ whose elements are all in $A$.