#include <bits/stdc++.h>
using namespace std;
int n, a[200020], b[200020], bc;
int mn[800020];
int ad[800020];
void build(int x, int l, int r) {
	if (l + 1 == r) {
		mn[x] = b[l];
		return;
	}
	int m = (l + r) / 2;
	build(x * 2 + 1, l, m);
	build(x * 2 + 2, m, r);
	mn[x] = min(mn[x * 2 + 1], mn[x * 2 + 2]);
	return;
}
void push(int x) {
	mn[x * 2 + 1] += ad[x];
	mn[x * 2 + 2] += ad[x];
	ad[x * 2 + 1] += ad[x];
	ad[x * 2 + 2] += ad[x];
	ad[x] = 0;
}
void change(int x, int l, int r, int L, int R) {
	if (L <= l && r <= R) {
		mn[x]++;
		ad[x]++;
		return;
	}
	if (r <= L || R <= l) {
		return;
	}
	push(x);
	int m = (l + r) / 2;
	change(x * 2 + 1, l, m, L, R);
	change(x * 2 + 2, m, r, L, R);
	mn[x] = min(mn[x * 2 + 1], mn[x * 2 + 2]);
}
int query(int x, int l, int r, int L, int R) {
	if (L <= l && r <= R) {
		return mn[x];
	}
	if (r <= L || R <= l) {
		return 2e9;
	}
	push(x);
	int m = (l + r) / 2;
	return min(query(x * 2 + 1, l, m, L, R), query(x * 2 + 2, m, r, L, R));
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
		b[i] = a[i];
	}
	sort(b, b + n);
	bc = unique(b, b + n) - b;
	build(0, 0, bc);
	long long z = 0;
	for (int i = 0; i < n; i++) {
		int p = lower_bound(b, b + bc, a[i]) - b;
		z += query(0, 0, bc, p, bc) - a[i];
		change(0, 0, bc, 0, p);
	}
	printf("%lld\n", z);
	return 0;
}
### Prompt

Develop a solution in CPP to the problem described below:

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;
int n, a[200020], b[200020], bc;
int mn[800020];
int ad[800020];
void build(int x, int l, int r) {
	if (l + 1 == r) {
		mn[x] = b[l];
		return;
	}
	int m = (l + r) / 2;
	build(x * 2 + 1, l, m);
	build(x * 2 + 2, m, r);
	mn[x] = min(mn[x * 2 + 1], mn[x * 2 + 2]);
	return;
}
void push(int x) {
	mn[x * 2 + 1] += ad[x];
	mn[x * 2 + 2] += ad[x];
	ad[x * 2 + 1] += ad[x];
	ad[x * 2 + 2] += ad[x];
	ad[x] = 0;
}
void change(int x, int l, int r, int L, int R) {
	if (L <= l && r <= R) {
		mn[x]++;
		ad[x]++;
		return;
	}
	if (r <= L || R <= l) {
		return;
	}
	push(x);
	int m = (l + r) / 2;
	change(x * 2 + 1, l, m, L, R);
	change(x * 2 + 2, m, r, L, R);
	mn[x] = min(mn[x * 2 + 1], mn[x * 2 + 2]);
}
int query(int x, int l, int r, int L, int R) {
	if (L <= l && r <= R) {
		return mn[x];
	}
	if (r <= L || R <= l) {
		return 2e9;
	}
	push(x);
	int m = (l + r) / 2;
	return min(query(x * 2 + 1, l, m, L, R), query(x * 2 + 2, m, r, L, R));
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
		b[i] = a[i];
	}
	sort(b, b + n);
	bc = unique(b, b + n) - b;
	build(0, 0, bc);
	long long z = 0;
	for (int i = 0; i < n; i++) {
		int p = lower_bound(b, b + bc, a[i]) - b;
		z += query(0, 0, bc, p, bc) - a[i];
		change(0, 0, bc, 0, p);
	}
	printf("%lld\n", z);
	return 0;
}
```