佩服nlogn的大根堆的做法；
但是这里只有n方的做法qwq；
正如lyd大佬的话，取自算法竞赛进阶指南；
B序列中所有数都在A中出现过；
证明：
对于n=1，显然成立。
设定理对N=k-1成立，
对于n=k-1时假设其满足由原数列的数构成最优解。那么，考虑对于n=k。
如果Bk-1<=Ak,那么令Bk=Ak即可；
否则Bk=Bk-1；命题仍成立，也可以结合中位数的知识；
我们设f[i][j]表示处理出来的序列长度为i，并且B的最后一位是j时的最小代价；
那么我们有转移方程：f[i][j]=min(f[i-1][k])+|Ai-j|(0=<k<=j);
书上说需要离散化，只需要知道j枚举的范围即可，所以我并没有写lower_bound；】
只是排了个序，去了个重；
然后我们将原序列翻转一下，在做一次dp，就得到了另一种情况，取min即可；

C++ 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans,f[2010][2010];
int n,m,A[2010],a[2010];
template<typename T>inline void read(T &x) {
    x=0;
    T f=1,ch=getchar();
    while (!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
    while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
    x*=f;
}
inline void dp() {
    for(int i=1;i<=n;i++) {
        ll minn=f[i-1][1];
        for(int j=1;j<=m;j++) {
            minn=min(minn,f[i-1][j]);
            f[i][j]=minn+abs(A[j]-a[i]);
        }
    }
}
int main() {
    read(n);
    for(int i=1;i<=n;i++) {
        read(a[i]);
        A[i]=a[i];
    }
    sort(A+1,A+n+1); m=unique(A+1,A+n+1)-A-1;
    dp();
    ans=f[n][1];
    for(int i=2;i<=m;i++) ans=min(ans,f[n][i]);
    reverse(a+1,a+n+1);
    dp();
    for(int i=1;i<=m;i++) ans=min(ans,f[n][i]);
    printf("%lld\n",ans);
}