【HNOI2002】营业额统计 //SPLAY TREE

//差不多能够徒手敲SPLAY了，继续努力
#include <cstdio>
const int MAXN = 40000;
const int INF = 1 << 30;
struct NODE
{
    int c[2], p, v, sz, mul;
    bool d;
}T[MAXN];
int n, root;
long long ans;
int abs(int x)
{
    if(x < 0)  return -x;
    return x;
}
void upd(int x)
{
    T[x].sz = T[T[x].c[0]].sz + T[T[x].c[1]].sz + T[x].mul;
}
void sc(int _p, int _c ,int _d)
{
    T[_p].c[_d] = _c;
    T[_c].p = _p;
    T[_c].d = _d;
}
void rot(int x)
{
    int y = T[x].p, d = T[x].d;
    if(y == root)
    {
        root = x;
        T[root].p = 0;
    }
    else
        sc(T[y].p, x, T[y].d);
    sc(y, T[x].c[!d], d);
    sc(x, y, !d);
    upd(y);
}
void splay(int x,int r)
{
    int i = x, p, p0;
    while((p0 = T[i].p) != r)
    {
        p = T[p0].p;
        if(p == r)  rot(i);
        else
        {
            if(T[i].d == T[p0].d)
            {
               rot(p0);
               rot(i);
            }
            else
            {
                rot(i);
                rot(i);
            }
        }
    }
    upd(x);
}
int ins(int _v)
{
    if(!root)
    {
        T[++n].v = _v;
        T[n].c[0] = T[n].c[1] = T[n].p = 0;
        T[n].mul = T[n].sz = 1;
        root = n;
        return 1;
    }
    int i = root, j;
    while(1)
    {
        T[i].sz++;
        if(T[i].v == _v)
        {
            T[i].mul++;
            splay(i, 0);
            return 0;
        }
        j = T[i].c[_v > T[i].v];
        if(!j) break;
        else i = j;
    }
    T[++n].v = _v;
    T[n].c[0] = T[n].c[1] = 0;
    T[n].mul = T[n].sz = 1;
    sc(i, n, _v > T[i].v);
    splay(n, 0);
    return 2;
}
int pred()
{
    int i = T[root].c[0], j;
    if(!i) return 0;
    while(j = T[i].c[1]) i = j;
    return i;
}
int succ()
{
    int i = T[root].c[1], j;
    if(!i) return 0;
    while(j = T[i].c[0]) i = j;
    return i;
}
int main()
{
    int x, y;
    int a, b, c, d;
    int m;
    while( scanf("%d", &m) != EOF)
    {
        n = 0;
        root = 0;
        ans = 0;
        for(int i = 0; i < m; i++)
        {
            scanf("%d", &x);
            y = ins(x);
            if(y == 0)  continue;  //有相同的点
            else if(y == 1) { ans += x; continue;}  //第一个根节点
            else
            {
                a = pred();
                b = succ();
                c = abs(T[a].v - x);
                d = abs(T[b].v - x);
                if(a == 0)  c = INF;
                if(b == 0)  d = INF;
                if(c > d) ans += d;
                else ans += c;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}