#include <stdio.h>
#include <vector>
#include <algorithm>
#include <climits>
#define SIZE 262144

struct info {
	int val, index;
};
std::pair<long long, int> lazy[SIZE * 2 + 1], tree[SIZE * 2 + 1], a[SIZE];
info input[SIZE];
std::vector<int> X;

void init(int node, int start, int end) {
	lazy[node] = std::make_pair(0, 0);
	if (start == end)
		tree[node] = a[start];
	else {
		init(node << 1, start, (start + end) >> 1);
		init((node << 1) | 1, ((start + end) >> 1) + 1, end);
		tree[node] = std::min(tree[node * 2], tree[node * 2 + 1]);
	}
}

void lazy_propagation(int node, int start, int end) {
	if (lazy[node].first != 0) {
		tree[node].first += lazy[node].first;
		if (start != end) {
			lazy[node << 1].first += lazy[node].first;
			lazy[(node << 1) | 1].first += lazy[node].first;
		}
		lazy[node] = std::make_pair(0, 0);
	}
}

void update(int node, int start, int end, int i, int j, long long val) {
	lazy_propagation(node, start, end);
	if (i > end || j < start)
		return;
	if (i <= start && end <= j) {
		tree[node].first += val;
		if (start != end) {
			lazy[node << 1].first += val;
			lazy[(node << 1) | 1].first += val;
		}
		return;
	}
	else {
		update(node << 1, start, (start + end) / 2, i, j, val);
		update((node << 1) | 1, (start + end) / 2 + 1, end, i, j, val);
		tree[node] = std::min(tree[node << 1], tree[(node << 1) | 1]);
	}
}

std::pair<long long, int> query(int node, int start, int end, int i, int j) {
	lazy_propagation(node, start, end);
	if (i > end || j < start)
		return std::make_pair(LLONG_MAX / 2, 0);
	if (i <= start && end <= j)
		return tree[node];
	return std::min(query(node * 2, start, (start + end) / 2, i, j), query(node * 2 + 1, (start + end) / 2 + 1, end, i, j));
}

int main(void) {
	int n;
	scanf("%d", &n);

	for (int i = 1; i <= n; i++) {
		scanf("%d", &input[i].val);
		X.push_back(input[i].val);
	}

	std::sort(X.begin(), X.end());
	X.erase(std::unique(X.begin(), X.end()), X.end());

	for (int i = 1; i <= n; i++) {
		input[i].index = std::lower_bound(X.begin(), X.end(), input[i].val) - X.begin() + 1;
	}

	int lastNode = X.size();

	for (int i = 1; i <= lastNode; i++)
		a[i] = std::make_pair(X[i - 1], i);

	init(1, 1, lastNode);
	long long r = 0;
	for (int i = 1; i <= n; i++) {
		std::pair<long long, int> q = query(1, 1, lastNode, input[i].index, lastNode);
		r = r + q.first - input[i].val;

		update(1, 1, lastNode, 1, q.second - 1, 1);
	}

	printf("%lld\n", r);
}
### 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 <stdio.h>
#include <vector>
#include <algorithm>
#include <climits>
#define SIZE 262144

struct info {
	int val, index;
};
std::pair<long long, int> lazy[SIZE * 2 + 1], tree[SIZE * 2 + 1], a[SIZE];
info input[SIZE];
std::vector<int> X;

void init(int node, int start, int end) {
	lazy[node] = std::make_pair(0, 0);
	if (start == end)
		tree[node] = a[start];
	else {
		init(node << 1, start, (start + end) >> 1);
		init((node << 1) | 1, ((start + end) >> 1) + 1, end);
		tree[node] = std::min(tree[node * 2], tree[node * 2 + 1]);
	}
}

void lazy_propagation(int node, int start, int end) {
	if (lazy[node].first != 0) {
		tree[node].first += lazy[node].first;
		if (start != end) {
			lazy[node << 1].first += lazy[node].first;
			lazy[(node << 1) | 1].first += lazy[node].first;
		}
		lazy[node] = std::make_pair(0, 0);
	}
}

void update(int node, int start, int end, int i, int j, long long val) {
	lazy_propagation(node, start, end);
	if (i > end || j < start)
		return;
	if (i <= start && end <= j) {
		tree[node].first += val;
		if (start != end) {
			lazy[node << 1].first += val;
			lazy[(node << 1) | 1].first += val;
		}
		return;
	}
	else {
		update(node << 1, start, (start + end) / 2, i, j, val);
		update((node << 1) | 1, (start + end) / 2 + 1, end, i, j, val);
		tree[node] = std::min(tree[node << 1], tree[(node << 1) | 1]);
	}
}

std::pair<long long, int> query(int node, int start, int end, int i, int j) {
	lazy_propagation(node, start, end);
	if (i > end || j < start)
		return std::make_pair(LLONG_MAX / 2, 0);
	if (i <= start && end <= j)
		return tree[node];
	return std::min(query(node * 2, start, (start + end) / 2, i, j), query(node * 2 + 1, (start + end) / 2 + 1, end, i, j));
}

int main(void) {
	int n;
	scanf("%d", &n);

	for (int i = 1; i <= n; i++) {
		scanf("%d", &input[i].val);
		X.push_back(input[i].val);
	}

	std::sort(X.begin(), X.end());
	X.erase(std::unique(X.begin(), X.end()), X.end());

	for (int i = 1; i <= n; i++) {
		input[i].index = std::lower_bound(X.begin(), X.end(), input[i].val) - X.begin() + 1;
	}

	int lastNode = X.size();

	for (int i = 1; i <= lastNode; i++)
		a[i] = std::make_pair(X[i - 1], i);

	init(1, 1, lastNode);
	long long r = 0;
	for (int i = 1; i <= n; i++) {
		std::pair<long long, int> q = query(1, 1, lastNode, input[i].index, lastNode);
		r = r + q.first - input[i].val;

		update(1, 1, lastNode, 1, q.second - 1, 1);
	}

	printf("%lld\n", r);
}
```