1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <cmath>
5 #include <algorithm>
6 using namespace std;
7 const int maxn=1e6;
8 int key[maxn],ch[maxn][2],fa[maxn],root,cnt;
9
10 void Rotate(int x)
11 {
12 int y=fa[x],g=fa[y],c=ch[y][1]==x;
13 ch[y][c]=ch[x][c^1];ch[x][c^1]=y;
14 fa[ch[y][c]]=y;fa[y]=x;fa[x]=g;
15 if(g)
16 ch[g][ch[g][1]==y]=x;
17 }
18
19 void Splay(int x)
20 {
21 for(int y;y=fa[x];Rotate(x))
22 if(fa[y])
23 Rotate((ch[fa[y]][1]==y)==(ch[y][1]==x)?y:x);
24 root=x;
25 }
26
27 void Insert(int x)
28 {
29 if(!root){
30 root=++cnt;
31 key[cnt]=x;
32 return;
33 }
34 int p=root,pre;
35 while(p)
36 {
37 pre=p;
38 p=ch[p][key[p]<x];
39 }
40 p=++cnt;fa[p]=pre;
41 ch[pre][key[pre]<x]=p;
42 key[p]=x;
43 Splay(p);
44 }
45 int Ql(int x)
46 {
47 int p=root,ret=-1000000000;
48 while(p){
49 if(key[p]<=x){
50 ret=max(ret,key[p]);
51 p=ch[p][1];
52 }
53 else p=ch[p][0];
54 }
55 return ret;
56 }
57 int Qr(int x)
58 {
59 int p=root,ret=1000000000;
60 while(p){
61 if(key[p]>=x){
62 ret=min(ret,key[p]);
63 p=ch[p][0];
64 }
65 else p=ch[p][1];
66 }
67 return ret;
68 }
69 int main()
70 {
71 int n,ans=0;
72 scanf("%d",&n);
73 for(int i=1;i<=n;i++)
74 {
75 int x=0;
76 scanf("%d",&x);
77 if(i==1){
78 ans=x;
79 Insert(x);
80 continue;
81 }
82 int l=Ql(x);
83 int r=Qr(x);
84 ans+=min(x-l,r-x);
85 Insert(x);
86 }
87 printf("%d\n",ans);
88 return 0;
89 }