#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=2e5+10;
const int inf=2147483647;

struct node
{
    int ch[2],fa,value,cnt,size;
};

int n,root,top;
node tree[N];

void pushup(int x);
void rotate(int x);
int get(int x);
void insert(int x);
void connect(int a,int b);
void splay(int x,int k);
int pre(int x);
int nxt(int x);

int get(int x)
{
    return x==tree[tree[x].fa].ch[1];
}

void pushup(int x)
{
    if(x==0)
        return;
    tree[x].size=tree[tree[x].ch[0]].size+tree[tree[x].ch[1]].size+tree[x].cnt;
    return;
}

void rotate(int x)
{
    int y=tree[x].fa;
    int z=tree[y].fa;
    int chk=get(x);
    tree[y].ch[chk]=tree[x].ch[chk^1];
    if(tree[x].ch[chk^1])
        tree[tree[x].ch[chk^1]].fa=y;
    tree[x].ch[chk^1]=y;
    tree[y].fa=x;
    if(z)
        tree[z].ch[y==tree[z].ch[1]]=x;
    tree[x].fa=z;
    pushup(y);
    pushup(x);
    return;
}

void splay(int x,int k)
{
    while(tree[x].fa!=k)
    {
        int y=tree[x].fa;
        int z=tree[y].fa;
        if(z!=k)
            if(get(x)==get(y))
                rotate(y);
            else
                rotate(x);
        rotate(x);
    }
    if(k==0)
        root=x;
    return;
}

void connect(int a,int b)
{
    tree[a].fa=b;
    tree[b].ch[tree[a].value>tree[b].value]=a;
    return;
}

void insert(int x)
{
    int u=root,fa=0;
    while(u)
    {
        if(tree[u].value==x)
        {
            tree[u].cnt++;
            pushup(u);
            pushup(fa);
            splay(u,0);
            return;
        }
        fa=u;
        u=tree[u].ch[x>tree[u].value];
    }
    u=++top;
    connect(u,fa);
    tree[u].value=x;
    tree[u].cnt=1;
    pushup(u);
    pushup(fa);
    splay(u,0);
    return;
}

int pre(int x)
{
    int cur=root;
    int res=-inf;
    while(cur)
    {
        if(x>tree[cur].value)
        {
            res=max(res,tree[cur].value);
            cur=tree[cur].ch[1];
        }
        else if(x==tree[cur].value)
            return tree[cur].value;
        else
            cur=tree[cur].ch[0];
    }
    return res;
}

//nxt：查询x的后继（定义为大于x的最小的数）
int nxt(int x)
{
    int cur=root;
    int res=inf;
    while(cur)
    {
        if(x<tree[cur].value)
        {
            res=min(res,tree[cur].value);
            cur=tree[cur].ch[0];
        }
        else if(x==tree[cur].value)
            return tree[cur].value;
        else
            cur=tree[cur].ch[1];
    }
    return res;
}

int main()
{
    cin>>n;
    int res=0;
    insert(inf);
    insert(-inf);
    for(int i=1;i<=n;i++)
    {
        int data,tmp=inf;
        cin>>data;
        int p=pre(data),ne=nxt(data);
        if(p!=-inf)
            tmp=min(tmp,max(p-data,data-p));
        if(ne!=inf)
            tmp=min(tmp,max(ne-data,data-ne));
        if(tmp==inf)
            tmp=data;
        res+=tmp;
        insert(data);
    }
    cout<<res<<endl;
    return 0;
}