#include<iostream>#include<cstring>#include<cstdio>#include<queue>#include<algorithm>using namespace std;typedef long long LL;#define N 55555int n,array[N];int stk[N],top;int elnum[N],delnum[N];struct node{ int l,r,dis,val;}LTree[N];int merge(int rx, int ry){ if(rx == 0) return ry; if(ry == 0) return rx; if(LTree[rx].val < LTree[ry].val) swap(rx,ry); LTree[rx].r = merge(LTree[rx].r,ry); int l,r; l = LTree[rx].l; r = LTree[rx].r; if(LTree[l].dis < LTree[r].dis) swap(LTree[rx].l,LTree[rx].r); if(LTree[rx].r == 0) LTree[rx].dis = 0; else LTree[rx].dis = LTree[LTree[rx].r].dis + 1; return rx;}int pop(int x){ int l,r; l = LTree[x].l; r = LTree[x].r; LTree[x].l = LTree[x].r = LTree[x].dis = 0; return merge(l,r);}int main(){ int i,j,k; while(scanf("%d",&n),n){ for(i = 1; i <= n; i++) scanf("%d",&array[i]); for(i = 1; i <= n; i++){ LTree[i].val = array[i]; LTree[i].l = LTree[i].r = LTree[i].dis = 0; } top = 0; for(i = 1; i <= n; i++){ stk[++top] = i; elnum[top] = 1; delnum[top] = 0; while(top > 1 && LTree[stk[top]].val <= LTree[stk[top-1]].val){ elnum[top-1] += elnum[top]; delnum[top-1] += delnum[top]; stk[top-1] = merge(stk[top-1],stk[top]); --top; while(delnum[top]*2+2 < elnum[top]){ stk[top] = pop(stk[top]); delnum[top]++; } } } LL ans = 0; int left = 1,right; for(i = 1; i <= top; i++){ right = left+elnum[i]-1; int mid = LTree[stk[i]].val; for(j = left; j <= right; j++) ans = ans + abs(mid-array[j]); left = right+1; } printf("%lldn",ans); }}
