/*
    给出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;
}