#define _CRT_SECURE_NO_DEPRECATE#include<stdio.h>  #include<string.h>  #include<cstring>#include<algorithm>  #include<queue>  #include<math.h>  #include<time.h>#include<vector>#include<iostream>using namespace std;typedef long long int LL;const int INF = 0x3f3f3f3f;typedef long long LL;namespace Scapegoat_Tree {#define MAXN (1000000 + 10)    const double alpha = 0.75;    struct Node {        Node * ch[2];        int key, size, cover; // size为有效节点的数量，cover为节点总数量         bool exist;    // 是否存在（即是否被删除）         void PushUp(void) {            size = ch[0]->size + ch[1]->size + (int)exist;            cover = ch[0]->cover + ch[1]->cover + 1;        }        bool isBad(void) { // 判断是否需要重构             return ((ch[0]->cover > cover * alpha + 5) ||                (ch[1]->cover > cover * alpha + 5));        }    };    struct STree {    protected:        Node mem_poor[MAXN]; //内存池，直接分配好避免动态分配内存占用时间         Node *tail, *root, *null; // 用null表示NULL的指针更方便，tail为内存分配指针，root为根         Node *bc[MAXN]; int bc_top; // 储存被删除的节点的内存地址，分配时可以再利用这些地址         Node * NewNode(int key) {            Node * p = bc_top ? bc[--bc_top] : tail++;            p->ch[0] = p->ch[1] = null;            p->size = p->cover = 1; p->exist = true;            p->key = key;            return p;        }        void Travel(Node * p, vector<Node *>&v) {            if (p == null) return;            Travel(p->ch[0], v);            if (p->exist) v.push_back(p); // 构建序列             else bc[bc_top++] = p; // 回收             Travel(p->ch[1], v);        }        Node * Divide(vector<Node *>&v, int l, int r) {            if (l >= r) return null;            int mid = (l + r) >> 1;            Node * p = v[mid];            p->ch[0] = Divide(v, l, mid);            p->ch[1] = Divide(v, mid + 1, r);            p->PushUp(); // 自底向上维护，先维护子树             return p;        }        void Rebuild(Node * &p) {            static vector<Node *>v; v.clear();            Travel(p, v); p = Divide(v, 0, v.size());        }        Node ** Insert(Node *&p, int val) {            if (p == null) {                p = NewNode(val);                return &null;            }            else {                p->size++; p->cover++;                // 返回值储存需要重构的位置，若子树也需要重构，本节点开始也需要重构，以本节点为根重构                 Node ** res = Insert(p->ch[val >= p->key], val);                if (p->isBad()) res = &p;                return res;            }        }        void Erase(Node *p, int id) {            p->size--;            int offset = p->ch[0]->size + p->exist;            if (p->exist && id == offset) {                p->exist = false;                return;            }            else {                if (id <= offset) Erase(p->ch[0], id);                else Erase(p->ch[1], id - offset);            }        }    public:        void Init(void) {            tail = mem_poor;            null = tail++;            null->ch[0] = null->ch[1] = null;            null->cover = null->size = null->key = 0;            root = null; bc_top = 0;        }        STree(void) { Init(); }        void Insert(int val) {            Node ** p = Insert(root, val);            if (*p != null) Rebuild(*p);        }        int Rank(int val) { //相同值取最小的排名            Node * now = root;            int ans = 1;            while (now != null) { // 非递归求排名                 if (now->key >= val) now = now->ch[0];                else {                    ans += now->ch[0]->size + now->exist;                    now = now->ch[1];                }            }            return ans;        }        int Kth(int k) { //支持相同值            Node * now = root;            while (now != null) { // 非递归求第K大                 if (now->ch[0]->size + 1 == k && now->exist) return now->key;                else if (now->ch[0]->size >= k) now = now->ch[0];                else k -= now->ch[0]->size + now->exist, now = now->ch[1];            }        }        void Erase(int k) {            Erase(root, Rank(k));            if (root->size < alpha * root->cover) Rebuild(root);        }        void Erase_kth(int k) {            Erase(root, k);            if (root->size < alpha * root->cover) Rebuild(root);        }    };#undef MAXN}using namespace Scapegoat_Tree;STree Scapegoat;int main(){    #ifdef kirito        freopen("in.txt","r",stdin);        freopen("out.txt","w",stdout);    #endif    //    int start = clock();    int n,val;    while (~scanf("%d", &n)){        LL sum=0;        for (int i = 1; i <= n; i++){            scanf("%d", &val);            if (i == 1){                sum += val;            }            else{                int valRank = Scapegoat.Rank(val);                int a = abs(Scapegoat.Kth(valRank) - val);                int b = abs(Scapegoat.Kth(valRank - 1) - val);                int c = abs(Scapegoat.Kth(val + 1) - val);                sum += min(a, min(b, c));            }            Scapegoat.Insert(val);        }        printf("%d\n", sum);        /* DEBUG INFO        vector<Node *> xx;        _t.Travel(_t.root, xx);        cout << "::";        for(int i = 0; i < xx.size(); i++) cout << xx[i]->key << ‘ ‘; cout << endl;        */    }    //#ifdef LOCAL_TIME    //    cout << "[Finished in " << clock() - start << " ms]" << endl;    //#endif    return 0;}

#define _CRT_SECURE_NO_DEPRECATE#include<stdio.h>  #include<string.h>  #include<cstring>#include<algorithm>  #include<queue>  #include<math.h>  #include<time.h>#include<vector>#include<iostream>using namespace std;typedef long long int LL;const int MAXN = 1e6 + 5;const int INF = 0x3f3f3f3f;int cnt, rt;struct Tree{    int key, size, fa, son[2];    void set(int _key, int _size, int _fa)    {        key = _key;        size = _size;        fa = _fa;        son[0] = son[1] = 0;    }}T[MAXN];inline void PushUp(int x){    T[x].size = T[T[x].son[0]].size + T[T[x].son[1]].size + 1;}inline void Rotate(int x, int p) {    int y = T[x].fa;    T[y].son[!p] = T[x].son[p];    T[T[x].son[p]].fa = y;    T[x].fa = T[y].fa;    if (T[x].fa)        T[T[x].fa].son[T[T[x].fa].son[1] == y] = x;    T[x].son[p] = y;    T[y].fa = x;    PushUp(y);    PushUp(x);}void Splay(int x, int To) {    while (T[x].fa != To)    {        if (T[T[x].fa].fa == To)            Rotate(x, T[T[x].fa].son[0] == x);        else        {            int y = T[x].fa, z = T[y].fa;            int p = (T[z].son[0] == y);            if (T[y].son[p] == x)                Rotate(x, !p), Rotate(x, p);             else                Rotate(y, p), Rotate(x, p);         }    }    if (To == 0) rt = x;}int find(int key) {    int x = rt;    while (x && T[x].key != key)        x = T[x].son[key > T[x].key];    if (x) Splay(x, 0);    return x;}int prev() {    int x = T[rt].son[0];    if (!x) return 0;    while (T[x].son[1])        x = T[x].son[1];    //Splay(x, 0);    return x;}int succ() {    int x = T[rt].son[1];    if (!x) return 0;    while (T[x].son[0])        x = T[x].son[0];    //Splay(x, 0);    return x;}void Insert(int key) {    if (!rt)        T[rt = cnt++].set(key, 1, 0);    else    {        int x = rt, y = 0;        while (x)        {            y = x;            x = T[x].son[key > T[x].key];        }        T[x = cnt++].set(key, 1, y);        T[y].son[key > T[y].key] = x;        Splay(x, 0);    }}void Delete(int key) {    int x = find(key);    if (!x) return;    int y = T[x].son[0];    while (T[y].son[1])        y = T[y].son[1];    int z = T[x].son[1];    while (T[z].son[0])        z = T[z].son[0];    if (!y && !z)    {        rt = 0;        return;    }    if (!y)    {        Splay(z, 0);        T[z].son[0] = 0;        PushUp(z);        return;    }    if (!z)    {        Splay(y, 0);        T[y].son[1] = 0;        PushUp(y);        return;    }    Splay(y, 0);    Splay(z, y);    T[z].son[0] = 0;    PushUp(z);    PushUp(y);}int GetPth(int p) {    if (!rt) return 0;    int x = rt, ret = 0;    while (x)    {        if (p == T[T[x].son[0]].size + 1)            break;        if (p>T[T[x].son[0]].size + 1)        {            p -= T[T[x].son[0]].size + 1;            x = T[x].son[1];        }        else            x = T[x].son[0];    }    Splay(x, 0);    return x;}int GetRank(int key) {    if (!rt) return 0;    int x = rt, ret = 0, y;    while (x)    {        y = x;        if (T[x].key <= key)        {            ret += T[T[x].son[0]].size + 1;            x = T[x].son[1];        }        else            x = T[x].son[0];    }    Splay(y, 0);    return ret;}int main(){    //#ifdef kirito    //    freopen("in.txt","r",stdin);    //    freopen("out.txt","w",stdout);    //#endif    //    int start = clock();    int n;    while (~scanf("%d", &n)){        LL ans = 0; rt = 0; cnt = 1; T[0].set(INF, 1, 0);        for (int i = 1; i <= n; i++){            int val; scanf("%d", &val);            Insert(val);            if (i == 1){ ans = val; }            else{                ans += min(abs(val - T[succ()].key), abs(val - T[prev()].key));            }        }        printf("%lld\n", ans);    }    //#ifdef LOCAL_TIME    //    cout << "[Finished in " << clock() - start << " ms]" << endl;    //#endif    return 0;}