#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

struct Node {
    int val, idx;
    Node() {}
    Node(int val, int idx) : val(val), idx(idx) {}
    bool operator <(Node a)const {
        if (val == a.val) {
            return idx < a.idx;
        }
        return val < a.val;
    }
};

/**
 * Segment Tree for calculating the sum of given range with lazy propagation
 * node     : Index of current node in the tree
 * cs...ce  : Covered range by the current node (0 base index)
 * qs...qe  : Query range (0 base index)
 */
class SegmentTree {
private:
    int size;
    vector<Node> tree;
    vector<int> lazy;

    Node init(const vector<int> &values, int node, int cs, int ce) {
        if (cs == ce)
            return tree[node] = { values[cs], cs };

        int mid = (cs + ce) / 2;
        return tree[node] = min(init(values, node * 2 + 1, cs, mid),
                            init(values, node * 2 + 2, mid + 1, ce));
    }

    Node search(int node, int cs, int ce, int qs, int qe) {
        if (qe < cs || ce < qs)
            return Node(1e9, 1e9); // NOTICE: Use the value that doesn't affect the result.

        propagate(node, cs, ce);

        if (qs <= cs && ce <= qe)
            return tree[node];

        int mid = (cs + ce) / 2;
        return min(search(node * 2 + 1, cs, mid, qs, qe),
               search(node * 2 + 2, mid + 1, ce, qs, qe));
    }

    int update(int node, int cs, int ce, int qs, int qe, int diff) {
        propagate(node, cs, ce);

        if (qe < cs || ce < qs)
            return tree[node].val;

        if (qs <= cs && ce <= qe) {
            if (cs < ce) {
                lazy[node * 2 + 1] += diff;
                lazy[node * 2 + 2] += diff;
            }
            return tree[node].val += diff;
        }

        int mid = (cs + ce) / 2;
        return tree[node].val = min(update(node * 2 + 1, cs, mid, qs, qe, diff),
                            update(node * 2 + 2, mid + 1, ce, qs, qe, diff));
    }

    void propagate(int node, int cs, int ce) {
        if (lazy[node] != 0) {
            tree[node].val += lazy[node];
            if (cs < ce) {
                lazy[node * 2 + 1] += lazy[node];
                lazy[node * 2 + 2] += lazy[node];
            }
            lazy[node] = 0;
        }
    }

public:
    void init(const vector<int> &values) {
        size = values.size();
        auto height = (int) ceil(log2(size));
        tree.resize(1 << (height + 1));
        lazy.resize(tree.size());
        init(values, 0, 0, size - 1);
    }

    Node search(int start, int end) {
        return search(0, 0, size - 1, start, end);
    }

    void update(int start, int end, int diff) {
        update(0, 0, size - 1, start, end, diff);
    }
};

int n;
int a[200002];
vector<int> v;
SegmentTree tree;

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        v.push_back(a[i]);
    }

    sort(v.begin(), v.end());
    v.resize(unique(v.begin(), v.end()) - v.begin());
    tree.init(v);

    long long ans = 0;
    for (int i = 0; i < n; i++) {
        auto pos = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
        auto ret = tree.search(pos, v.size()-1);
        ans += ret.val - a[i];
        tree.update(0, ret.idx-1, 1);
    }

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

    return 0;
}

### Prompt

Your challenge is to write a cpp solution to the following problem:

We have a sequence A of length N.

On this sequence, we can perform the following two kinds of operations:

* Swap two adjacent elements.

* Select one element, and increment it by 1.




We will repeatedly perform these operations so that A will be a non-decreasing sequence. Find the minimum required number of operations.

Constraints

* 1 ≤ N ≤ 200000
* 1 ≤ A_i ≤ 10^9
* A_i is an integer.

Input

Input is given from Standard Input in the following format:


N
A_1
A_2
:
A_N


Output

Print the minimum number of operations required to turn A into a non-decreasing sequence.

Examples

Input

5
4
1
8
8
7


Output

2


Input

20
8
2
9
7
4
6
7
9
7
4
7
4
4
3
6
2
3
4
4
9


Output

62

### Response

```cpp
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

struct Node {
    int val, idx;
    Node() {}
    Node(int val, int idx) : val(val), idx(idx) {}
    bool operator <(Node a)const {
        if (val == a.val) {
            return idx < a.idx;
        }
        return val < a.val;
    }
};

/**
 * Segment Tree for calculating the sum of given range with lazy propagation
 * node     : Index of current node in the tree
 * cs...ce  : Covered range by the current node (0 base index)
 * qs...qe  : Query range (0 base index)
 */
class SegmentTree {
private:
    int size;
    vector<Node> tree;
    vector<int> lazy;

    Node init(const vector<int> &values, int node, int cs, int ce) {
        if (cs == ce)
            return tree[node] = { values[cs], cs };

        int mid = (cs + ce) / 2;
        return tree[node] = min(init(values, node * 2 + 1, cs, mid),
                            init(values, node * 2 + 2, mid + 1, ce));
    }

    Node search(int node, int cs, int ce, int qs, int qe) {
        if (qe < cs || ce < qs)
            return Node(1e9, 1e9); // NOTICE: Use the value that doesn't affect the result.

        propagate(node, cs, ce);

        if (qs <= cs && ce <= qe)
            return tree[node];

        int mid = (cs + ce) / 2;
        return min(search(node * 2 + 1, cs, mid, qs, qe),
               search(node * 2 + 2, mid + 1, ce, qs, qe));
    }

    int update(int node, int cs, int ce, int qs, int qe, int diff) {
        propagate(node, cs, ce);

        if (qe < cs || ce < qs)
            return tree[node].val;

        if (qs <= cs && ce <= qe) {
            if (cs < ce) {
                lazy[node * 2 + 1] += diff;
                lazy[node * 2 + 2] += diff;
            }
            return tree[node].val += diff;
        }

        int mid = (cs + ce) / 2;
        return tree[node].val = min(update(node * 2 + 1, cs, mid, qs, qe, diff),
                            update(node * 2 + 2, mid + 1, ce, qs, qe, diff));
    }

    void propagate(int node, int cs, int ce) {
        if (lazy[node] != 0) {
            tree[node].val += lazy[node];
            if (cs < ce) {
                lazy[node * 2 + 1] += lazy[node];
                lazy[node * 2 + 2] += lazy[node];
            }
            lazy[node] = 0;
        }
    }

public:
    void init(const vector<int> &values) {
        size = values.size();
        auto height = (int) ceil(log2(size));
        tree.resize(1 << (height + 1));
        lazy.resize(tree.size());
        init(values, 0, 0, size - 1);
    }

    Node search(int start, int end) {
        return search(0, 0, size - 1, start, end);
    }

    void update(int start, int end, int diff) {
        update(0, 0, size - 1, start, end, diff);
    }
};

int n;
int a[200002];
vector<int> v;
SegmentTree tree;

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        v.push_back(a[i]);
    }

    sort(v.begin(), v.end());
    v.resize(unique(v.begin(), v.end()) - v.begin());
    tree.init(v);

    long long ans = 0;
    for (int i = 0; i < n; i++) {
        auto pos = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
        auto ret = tree.search(pos, v.size()-1);
        ans += ret.val - a[i];
        tree.update(0, ret.idx-1, 1);
    }

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

    return 0;
}

```