#include<bits/stdc++.h>
using namespace std;
struct node
{
    int ch[2],p,cnt,size,k;
}tree[32767];
int root,tot;
#define l(x) tree[x].ch[0]
#define r(x) tree[x].ch[1]
#define k(x) tree[x].k
#define siz(x) tree[x].size
#define cnt(x) tree[x].cnt
#define p(x) tree[x].p
void get_size(int x)
{
    siz(x)=siz(l(x))+siz(r(x))+cnt(x);
}
void rotate(int x)
{
    int y=p(x);
    int z=p(y);
    int b=tree[y].ch[1]==x;
    tree[z].ch[tree[z].ch[1]==y]=x;
    p(x)=z;
    tree[y].ch[b]=tree[x].ch[b^1];
    tree[tree[x].ch[b^1]].p=y;
    tree[x].ch[b^1]=y;
    tree[y].p=x;
    get_size(y);
    get_size(x);
}
int gett(int x)
{
    return l(p(x))==x?1:0;
}
void splay(int x)
{
    for(int y=p(x); y=p(x),y; rotate(x))
    if(p(y))
    rotate(gett(x)==gett(y)?y:x);
    root=x;
}
void splay_insert(int x)
{
    if(root==0)
    {
        k(++tot)=x;
        cnt(tot)++;
        root=tot;
        get_size(root);
        return;
    }
    int now=root,father=0;
    while(1)
    {
        if(k(now)==x)
        {
            cnt(now)++;
            get_size(now);
            get_size(father);
            splay(now);
            break;
        }
        father=now;
        now=tree[father].ch[x>k(father)];
        if(!now)
        {
            k(++tot)=x;
            cnt(tot)++;
            p(tot)=father;
            if(k(father)<x) r(father)=tot;
            else l(father)=tot;
            get_size(tot);
            get_size(father);
            splay(tot);
            break;
        }
    }
}
int biggest(int x)
{
    if(r(x)==0)return x;
    return biggest(r(x));
}
int smallest(int x)
{
    if(l(x)==0)return x;
    return smallest(r(x));
}
int n,ans;
int main()
{
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        int x;cin>>x;
        if(i==1)ans+=x,splay_insert(x);
        else
        {
            splay_insert(x);
            if(cnt(root)<=1)
            {
                int a=-1,b=-1;
                if(l(root)!=0)a=biggest(l(root));
                if(r(root)!=0)b=smallest(r(root));
                if(a==-1)a=0x3f3f3f3f;
                else a=abs(k(a)-x);
                if(b==-1)b=0x3f3f3f3f;
                else b=abs(k(b)-x);
                ans=ans+min(a,b);
            }
        }
    }
    cout<<ans<<endl;
}