rt.

#include<bits/stdc++.h>
#define int long long
#define il inline
using namespace std;

const int N = 100005;
int n, m, x, ret, det, tl, tr, ans;

struct Treap{
	int tot, root, INF = 0x3f3f3f3f;
	struct node{
		int l, r, sn;
		int fa, v, det, cnt;
	}t[N];
	il int create(int x){
		t[++tot].v = x;
		t[tot].sn = 1;
		t[tot].det = rand();
		return tot;
	}
	il void up(int x){
		t[x].sn = t[t[x].l].sn + t[t[x].r].sn + 1;
	}
	il void split(int p, int v, int &l, int &r){
		if (!p){
			l = r = 0;
			return ;
		}
		if (t[p].v <= v){
			l = p;
			split(t[l].r, v, t[l].r, r);
		}
		else{
			r = p;
			split(t[r].l, v, l, t[r].l);
		}
		up(p);
	}
	il int merge(int l, int r){
		if (!l || !r) return l | r;
		if (t[l].det < t[r].det){
			t[l].r = merge(t[l].r, r);
			up(l);
			return l;
		}
		else{
			t[r].l = merge(l, t[r].l);
			up(r);
			return r;
		}
	}
	il void ins(int v){
		split(root, v - 1, tl, tr);
		root = merge(merge(tl, create(v)), tr);
	}
	il void del(int v){
		int tmp;
		split(root, v - 1, tl, tr);
		split(tr, v, tmp, tr);
		tmp = merge(t[tmp].l, t[tmp].r);
		root = merge(tl, merge(tmp, tr));
	}
	il int find_kth(int v){
		split(root, v - 1, tl, tr);
		int rk = t[tl].sn + 1;
		root = merge(tl, tr);
		return rk;
	}
	il int kth_find(int p, int k){
		int ln = t[t[p].l].sn + 1;
		if (ln == k) return t[p].v;
		else if (ln < k) return kth_find(t[p].r, k - ln);
		else return kth_find(t[p].l, k);
	}
	il int pre(int v){
		split(root, v - 1, tl, tr);
		int tmp = kth_find(tl, t[tl].sn);
		root = merge(tl, tr);
		return tmp;
	}
	il int nxt(int v){
		split(root, v, tl, tr);
		int tmp = kth_find(tr, 1);
		root = merge(tl, tr);
		return tmp;
	}
}fhq;

signed main(){
	srand(time(NULL));
	cin >> n >> x;
	ans += x;
	fhq.ins(x);
	for (int i = 2; i <= n; i++){
		cin >> x;
		int pe = x - fhq.pre(x), nt = fhq.nxt(x) - x;
		ans += min(pe, nt);
		fhq.ins(x);
	}
	cout << ans;
	return 0;
}