Code

#include <bits/stdc++.h>
#define ll long long
#define inf 0x7fffffff
#define maxn 35010
using namespace std;
int x=0,flag=1;char ch=getchar();
while(!isdigit(ch)&&ch!='-') ch=getchar();
if (ch=='-') flag=-1,ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch-'0'),ch=getchar();
return x*flag;
}
int len,n,a[maxn],dp[maxn];
ll s[maxn],p[maxn],f[maxn];
vector<int>to[maxn];
ll abss(ll x){return x>0?x:-x;}
int main(){
for (int i=1;i<=n;++i)
f[len]=-inf;a[n+1]=inf;
for (int i=1;i<=n+1;++i){
if (a[i]>=f[len]) f[++len]=a[i],dp[i]=len;
else{
int k=upper_bound(f+1,f+1+len,a[i])-f;
f[k]=a[i];dp[i]=k;
}
}
printf("%d\n",n-len+1);
memset(f,0x3f,sizeof(f));f[0]=0;a[0]=-inf;
for (int i=0;i<=n;++i) to[dp[i]].push_back(i);
for (int u=1;u<=n+1;++u){
for (int j=0;j<to[dp[u]-1].size();++j){
int v=to[dp[u]-1][j];
if (v>=u||a[v]>a[u]) continue;
s[v-1]=p[v-1]=0;
for (int i=v;i<=u;++i)
s[i]=s[i-1]+abss(a[i]-a[v]),
p[i]=p[i-1]+abss(a[i]-a[u]);
for (int k=v-1;k<=u;++k)
f[u]=min(f[u],f[v]+s[k]-s[v-1]+p[u]-p[k]);
}
}
printf("%lld\n",f[n+1]);
}