#include <bits/stdc++.h>

 #define INF 1000000000

 using namespace std;

 int root,N,n,x;

 int fa[],c[][],a[];

 void rot(int x)

 {

     int fat=fa[x],k=c[fat][]==x;

     c[fat][k]=c[x][!k];fa[c[x][!k]]=fat;

     fa[x]=fa[fat];c[fa[fat]][c[fa[fat]][]==fat]=x;

     fa[fat]=x;c[x][!k]=fat;

 }

 void splay(int x,int g)

 {

     for(int y;(y=fa[x])!=g;rot(x))

     if(fa[y]!=g)

     if((c[y][]==x)==(c[fa[y]][]==y)) rot(y);else rot(x);

     if(g==) root=x;

 }

 int lower(int p)

 {

     if(!root) return ;

     int ans=INF;

     for(int i=root;i;(p>=a[i])?i=c[i][]:i=c[i][])

     if(a[i]>=p)

         ans=min(ans,a[i]);

     return ans-p;

 }

 int upper(int p)

 {

     if(!root) return ;

     int ans=-INF;

     for(int i=root;i;(p>=a[i])?i=c[i][]:i=c[i][])

     if(a[i]<=p)

         ans=max(ans,a[i]);

     return p-ans;

 }

 void add(int x)

 {

     a[++N]=x;c[N][]=c[N][]=;

     if(!root)

     {

         root=N;

         return;

     }

     for(int i=root;;)

     if(x<=a[i])

         if(!c[i][])

         {

             c[i][]=N,fa[N]=i;

             splay(N,);

             break;

         }

         else i=c[i][];

     else

         if(!c[i][])

         {

             c[i][]=N,fa[N]=i;

             splay(N,);

             break;

         }

         else i=c[i][];

 }

 int main()

 {

     scanf("%d",&n);int ans=;

     for(int i=;i<=n;i++)

     {

         scanf("%d",&x);

         if(i==) ans+=x;

         else

             ans+=min(upper(x),lower(x));

         add(x);

     }

     printf("%d\n",ans);

     return ;

 }