#include <bits/stdc++.h>

using namespace std;

struct SegTree {
  int n; vector<int> data, lazy;
  SegTree(vector<int> v) : n(v.size()), data(4 * n), lazy(4 * n) {
    init(1, 0, n - 1, v);
  }

  void Update(int l) { update(1, 0, n - 1, l); }
  int Query(int l) { return query(1, 0, n - 1, l); }

  void push(int node, int b, int e) {
    if (lazy[node] == 0) return;
    data[node] += lazy[node];
    if (b != e) {
      lazy[node * 2] += lazy[node];
      lazy[node * 2 + 1] += lazy[node];
    }
    lazy[node] = 0;
  }

  void init(int node, int b, int e, vector<int>& v) {
    if (b == e) {
      data[node] = v[b];
    } else {
      int m = (b + e) / 2;
      init(node * 2, b, m, v);
      init(node * 2 + 1, m + 1, e, v);
      data[node] = min(data[node * 2], data[node * 2 + 1]);
    }
  }

  void update(int node, int b, int e, int l) {
    push(node, b, e);
    if (e < l) return;
    if (b >= l) {
      lazy[node] -= 1;
      push(node, b, e);
    } else {
      int m = (b + e) / 2;
      update(node * 2, b, m, l);
      update(node * 2 + 1, m + 1, e, l);
      data[node] = min(data[node * 2], data[node * 2 + 1]);
    }
  }

  int query(int node, int b, int e, int l) {
    push(node, b, e);
    if (e < l) return 2e9;
    if (b >= l) {
      return data[node];
    }
    int m = (b + e) / 2;
    return min(query(node * 2, b, m, l), 
        query(node * 2 + 1, m + 1, e, l));
  }
};

int main() {
  int n; cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }

  vector<int> all = a;
  all.push_back(0);
  sort(all.begin(), all.end());
  all.erase(unique(all.begin(), all.end()), all.end());
  auto norm = [&](int x) {
    auto it = lower_bound(all.begin(), all.end(), x);
    return it - all.begin();
  };
  SegTree st(all);
  

  long long ans = 0;
  for (int i = 0; i < n; ++i) {
    int ai = a[i];
    int nai = norm(ai);
    int stq = st.Query(nai);
    ans += stq - a[i] + i;
    st.Update(nai);
  }
  cout << ans << endl;

  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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;

struct SegTree {
  int n; vector<int> data, lazy;
  SegTree(vector<int> v) : n(v.size()), data(4 * n), lazy(4 * n) {
    init(1, 0, n - 1, v);
  }

  void Update(int l) { update(1, 0, n - 1, l); }
  int Query(int l) { return query(1, 0, n - 1, l); }

  void push(int node, int b, int e) {
    if (lazy[node] == 0) return;
    data[node] += lazy[node];
    if (b != e) {
      lazy[node * 2] += lazy[node];
      lazy[node * 2 + 1] += lazy[node];
    }
    lazy[node] = 0;
  }

  void init(int node, int b, int e, vector<int>& v) {
    if (b == e) {
      data[node] = v[b];
    } else {
      int m = (b + e) / 2;
      init(node * 2, b, m, v);
      init(node * 2 + 1, m + 1, e, v);
      data[node] = min(data[node * 2], data[node * 2 + 1]);
    }
  }

  void update(int node, int b, int e, int l) {
    push(node, b, e);
    if (e < l) return;
    if (b >= l) {
      lazy[node] -= 1;
      push(node, b, e);
    } else {
      int m = (b + e) / 2;
      update(node * 2, b, m, l);
      update(node * 2 + 1, m + 1, e, l);
      data[node] = min(data[node * 2], data[node * 2 + 1]);
    }
  }

  int query(int node, int b, int e, int l) {
    push(node, b, e);
    if (e < l) return 2e9;
    if (b >= l) {
      return data[node];
    }
    int m = (b + e) / 2;
    return min(query(node * 2, b, m, l), 
        query(node * 2 + 1, m + 1, e, l));
  }
};

int main() {
  int n; cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }

  vector<int> all = a;
  all.push_back(0);
  sort(all.begin(), all.end());
  all.erase(unique(all.begin(), all.end()), all.end());
  auto norm = [&](int x) {
    auto it = lower_bound(all.begin(), all.end(), x);
    return it - all.begin();
  };
  SegTree st(all);
  

  long long ans = 0;
  for (int i = 0; i < n; ++i) {
    int ai = a[i];
    int nai = norm(ai);
    int stq = st.Query(nai);
    ans += stq - a[i] + i;
    st.Update(nai);
  }
  cout << ans << endl;

  return 0;
}

```