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<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 &\left|\hat{a}_1-a_1\right|+\cdots+\left|\hat{a}_n-a_n\right| \\ \text{subject to}\quad &\hat{a}_1\ge\cdots\ge\hat{a}_n \end{align*} $$
or equivalentlly
$$ \begin{align*} \text{minimize}\quad &t_1+\cdots+t_n \\ \text{subject to}\quad &\hat{a}_i-a_i\le t_i, &i=1,\ldots,n\\ &-\left(\hat{a}_i-a_i\right)\le t_i, &i=1,\ldots,n\\ &\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.