/*
    給出n<=50000個數的序列a[1]..a[n]，求一個非遞減的序列b[1]..b[n]
    使得∑|a[i]-b[i]|最小

    如果只是求一個點x，使得∑|a[i]-b[i]|最小，顯然x = a[(n+1)/2]（中位數）---------------OMG
    但現在可以有多個點，如果a[]是遞增的，那么令b[i] = a[i]即可了
    現在a[]是無規律的

    左偏樹的論文題，看了論文還不完全懂
    做法：
    最后答案的形式是將1..n分成m個連續的區間，每個區間的b[i]是一樣的，且不同區間是非遞減的
    在檢查n時，假設1..n-1已經分成了m個區間了
    現在先把a[n]單獨一個區間，顯然b[n]=a[n]會是1..n的最優值（因為前面1..n-1是最優的，而第n個
    對答案的貢獻為0），但是不一定滿足b[n-1]<=b[n]，算法為：
    若b[n-1] <= b[n]，則b[n]就是a[n]了
    否則，需要合并目前最尾的兩個區間，直至這兩個區間有b[k] <= b[k+1]              -------OMG
    而b[k]顯然是每一個區間的中位數了
    合并兩個區間求中位數，可用左偏樹做最大堆分別維護每個區間的前(ni+1)/2小的數，-------OMG
    則堆頂為每個    區間的中位數了，合并時，將右邊區間的那些數合并到左邊即可
    O(nlogn)
    左偏樹真是神奇漂亮的東西!!

    至于為什么是合并最后兩個區間，將第n個數和它之前那個區間的一部分數合起來不行嗎？
    假設a[kn-1]是求出來的一個區間，則肯定有a[n-1]<a[k..n-2]的中位數，否則將a[n-1]獨立出來會更優---OMG
    同理，a[n]<a[k..n-1]的中位數，需要進行合并，那能不能a[kn]分成兩部分，而不是合并成一部分呢？
    即a[k..k'], a[k'..n]，這樣也不行，由假設知，肯定a[k'..n]的中位數<a[k..k']的中位數，需要合并
    （大于的話，a[k'+1..n-1]就不會合并到那里去啦~~）
*/
#include<iostream>
#include<cstring>
#include<map>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstring>
#include<cmath>
#include<string>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<set>
#include<list>
#include<numeric>
#include<cassert>
#include<sstream>
#include<ctime>
#include<bitset>
#include<functional>

using namespace std;

const int MAXN = 100010;

struct Node 
{
    int key, dist, lc, rc;
};

Node nodes[MAXN];
int alloc;

void initNode()
{
    nodes[0].dist = -1;//0作為NULL節點
    alloc = 1;
}

int newNode(int x)
{
    nodes[alloc].key = x;
    nodes[alloc].dist = 0;
    nodes[alloc].lc = nodes[alloc].rc = 0;
    return alloc++;
}

int merge(int A, int B)
{
    if (A != 0 && B != 0) {
        if (nodes[A].key < nodes[B].key) {//
            swap(A, B);
        }
        nodes[A].rc = merge(nodes[A].rc, B);
        int &lc = nodes[A].lc;
        int &rc = nodes[A].rc;
        if (nodes[lc].dist < nodes[rc].dist) {
            swap(lc, rc);
        }
        nodes[A].dist = nodes[rc].dist + 1;
    } else {
        A = A == 0 ? B : A;
    }
    return A;
}


int pop(int A)
{
    int t = merge(nodes[A].lc, nodes[A].rc);
    nodes[A].lc = nodes[A].rc = 0;//隔離出A后記得將A的兒子也清空
    return t;
}

int a[MAXN];

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif

    for (int n;scanf("%d", &n), n; ) {
        initNode();
        stack<pair<int,int> > S;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            pair<int, int> np(newNode(a[i]), 1);//node, len
            while (!S.empty() && nodes[S.top().first].key > nodes[np.first].key) {
                pair<int,int> top = S.top();
                S.pop();
                int n1 = top.second, n2 = np.second;
                np.first = merge(top.first, np.first);
                np.second = n1+n2;
                if ((n1+1)/2 + (n2+1)/2 > (n1+n2+1)/2) {
                    np.first = pop(np.first);
                }
            }
            S.push(np);
        }
        long long ans = 0;
        int id = n;
        while (!S.empty()) {
            int b = nodes[S.top().first].key, num = S.top().second;
            S.pop();
            while (num -- > 0) {
                ans += abs(a[id--] - b);
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}