#include <bits/stdc++.h>

using namespace std;

const int maxn = 200005;
const int treesize = 1 << 18;

int tree[2 * treesize];
int add[2 * treesize];
int a[maxn], pos[maxn];
vector<int> xs;
int n;

int getans(int cur)
{
    return tree[cur] + add[cur];
}

void push(int cur)
{
    tree[cur] += add[cur];
    add[cur * 2] += add[cur];
    add[cur * 2 + 1] += add[cur];
    add[cur] = 0;
}

void update(int cur)
{
    tree[cur] = max(getans(cur * 2), getans(cur * 2 + 1));
}

int get(int cur, int cl, int cr, int l, int r)
{
    if (cl > r || cr < l) return (int)(-1e9);
    if (cl >= l && cr <= r) return getans(cur);
    int cm = (cl + cr) / 2;
    push(cur);
    return max(get(cur * 2, cl, cm, l, r), get(cur * 2 + 1, cm + 1, cr, l, r));
}

void addd(int cur, int cl, int cr, int l, int r, int t)
{
    if (cl > r || cr < l) return;
    if (cl >= l && cr <= r)
    {
        add[cur] += t;
        return;
    }
    int cm = (cl + cr) / 2;
    push(cur);
    addd(cur * 2, cl, cm, l, r, t);
    addd(cur * 2 + 1, cm + 1, cr, l, r, t);
    update(cur);
}

int t[maxn];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
        xs.push_back(a[i]);
    }
    sort(xs.begin(), xs.end());
    xs.resize(unique(xs.begin(), xs.end()) - xs.begin());
    for (int i = 0; i < n; i++) pos[i] = lower_bound(xs.begin(), xs.end(), a[i]) - xs.begin();
    long long answer = 0;
    for (int i = 0; i < n; i++)
    {
        addd(1, 0, treesize - 1, 0, pos[i] - 1, 1);
        answer += t[i] = get(1, 0, treesize - 1, pos[i], pos[i]);
    }
    for (int i = 0; i < n; i++)
    {
        addd(1, 0, treesize - 1, 0, pos[i] - 1, -1);
    }
    for (int i = 0; i < n; i++)
    {
        addd(1, 0, treesize - 1, pos[i], xs.size(), 1);
    }
    for (int i = 0; i < (int)xs.size(); i++) addd(1, 0, treesize - 1, i, i, -xs[i]);
//     for (int i = 0; i < (int)xs.size(); i++) cout << get(1, 0, treesize - 1, i, i) << endl;
//     cout << answer << endl;
    for (int i = n - 1; i >= 0; i--)
    {
        addd(1, 0, treesize - 1, pos[i], xs.size(), -1);
//         cout << get(1, 0, treesize - 1, pos[i], xs.size() - 1) + xs[pos[i]] - (i - t[i]) << endl;
        answer -= (get(1, 0, treesize - 1, pos[i], xs.size() - 1) + xs[pos[i]] - (i - t[i]));
    }
    cout << answer << endl;
    
}
### Prompt

In CPP, your task is to solve 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 <bits/stdc++.h>

using namespace std;

const int maxn = 200005;
const int treesize = 1 << 18;

int tree[2 * treesize];
int add[2 * treesize];
int a[maxn], pos[maxn];
vector<int> xs;
int n;

int getans(int cur)
{
    return tree[cur] + add[cur];
}

void push(int cur)
{
    tree[cur] += add[cur];
    add[cur * 2] += add[cur];
    add[cur * 2 + 1] += add[cur];
    add[cur] = 0;
}

void update(int cur)
{
    tree[cur] = max(getans(cur * 2), getans(cur * 2 + 1));
}

int get(int cur, int cl, int cr, int l, int r)
{
    if (cl > r || cr < l) return (int)(-1e9);
    if (cl >= l && cr <= r) return getans(cur);
    int cm = (cl + cr) / 2;
    push(cur);
    return max(get(cur * 2, cl, cm, l, r), get(cur * 2 + 1, cm + 1, cr, l, r));
}

void addd(int cur, int cl, int cr, int l, int r, int t)
{
    if (cl > r || cr < l) return;
    if (cl >= l && cr <= r)
    {
        add[cur] += t;
        return;
    }
    int cm = (cl + cr) / 2;
    push(cur);
    addd(cur * 2, cl, cm, l, r, t);
    addd(cur * 2 + 1, cm + 1, cr, l, r, t);
    update(cur);
}

int t[maxn];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
        xs.push_back(a[i]);
    }
    sort(xs.begin(), xs.end());
    xs.resize(unique(xs.begin(), xs.end()) - xs.begin());
    for (int i = 0; i < n; i++) pos[i] = lower_bound(xs.begin(), xs.end(), a[i]) - xs.begin();
    long long answer = 0;
    for (int i = 0; i < n; i++)
    {
        addd(1, 0, treesize - 1, 0, pos[i] - 1, 1);
        answer += t[i] = get(1, 0, treesize - 1, pos[i], pos[i]);
    }
    for (int i = 0; i < n; i++)
    {
        addd(1, 0, treesize - 1, 0, pos[i] - 1, -1);
    }
    for (int i = 0; i < n; i++)
    {
        addd(1, 0, treesize - 1, pos[i], xs.size(), 1);
    }
    for (int i = 0; i < (int)xs.size(); i++) addd(1, 0, treesize - 1, i, i, -xs[i]);
//     for (int i = 0; i < (int)xs.size(); i++) cout << get(1, 0, treesize - 1, i, i) << endl;
//     cout << answer << endl;
    for (int i = n - 1; i >= 0; i--)
    {
        addd(1, 0, treesize - 1, pos[i], xs.size(), -1);
//         cout << get(1, 0, treesize - 1, pos[i], xs.size() - 1) + xs[pos[i]] - (i - t[i]) << endl;
        answer -= (get(1, 0, treesize - 1, pos[i], xs.size() - 1) + xs[pos[i]] - (i - t[i]));
    }
    cout << answer << endl;
    
}
```