Transforming an array into one with descending order Problem Description

Given an array $A$ of $n$ integers, find the minimum number of operations to turn it into a new array $\widehat{A}$ with a (weakly) descending order: we require that $\hat{a}_i \geq \hat{a}_j$ for all $1\leq i&lt;j\leq n$. Here an operation means either increasing or decreasing an element by $1$.

For example, it requires at least $4$ operations to turn the array $[1,2,3,4]$ into descending order. One solution is increasing the first element by $2$, increasing the second element by $1$, and decreasing the last element by $1$ (then the new array is $[3,3,3,3]$, which is in decending order).

My questions:


Is the problem NP-hard?
If not, what algorithm solves this problem with the best time complexity?


My efforts

We can write this problem as an integer linear programming. Say the elements in the array are $a_1,a_2,\ldots,a_n$, and those in the new array are $\hat{a}_1,\ldots,\hat{a}_n$ then the problem is essentially an interger programming:

$$ 
\begin{align*}
\text{minimize}\quad &amp;\left|\hat{a}_1-a_1\right|+\cdots+\left|\hat{a}_n-a_n\right| \\
\text{subject to}\quad &amp;\hat{a}_1\ge\cdots\ge\hat{a}_n
\end{align*}
$$

or equivalentlly

$$ 
\begin{align*}
\text{minimize}\quad &amp;t_1+\cdots+t_n \\
\text{subject to}\quad &amp;\hat{a}_i-a_i\le t_i, &amp;i=1,\ldots,n\\
&amp;-\left(\hat{a}_i-a_i\right)\le t_i, &amp;i=1,\ldots,n\\
&amp;\hat{a}_1\ge\cdots\ge\hat{a}_n
\end{align*}
$$

But it seems not to help because the coefficient matrix is not totally unimodular, thus we cannot relax it to linear programming.

I also find a property of optimum solutions:


  If some consecutive elements are originally in non-descending order, then they must be the same in an optimum solution. 


I don't know whether this property helps.
There is an efficient dynamic programming solution if the input domain is small.

Let $C_i(v)$ be the cost of increasing/reducing elements such that $\hat a_i = v \wedge (\forall j &gt;i)[\hat a_{j} \leq v]$.

It should be obvious that $C_n(v)$ is simply $|a_n - v|$, and thus computing $C_n$ completely is easy.

Then $C_{i}(v)$ is $|a_i - v| + \min(C_{i+1}(0), C_{i+1}(1),\dots,C_{i+1}(v))$. Using this we can compute $C$ as a table, using $C_{i+1}$ to fill $C_i$, working backwards all the way to $C_1$. Then choosing the minimal element of $C_1$ and working forwards again you have found the solution.