#include <bits/stdc++.h>
using namespace std;

const int N = 200005;
const int INF = 1e9;

int n, a[N];
int lazy[4 * N], it[4 * N];
long long res;
vector<int> val;

void build(int i, int l, int r) {
	if (l == r) {
		it[i] = val[l]; return;
	}
	int mid = (l + r) >> 1;
	build(i << 1, l, mid), build(i << 1 | 1, mid + 1, r);
	it[i] = min(it[i << 1], it[i << 1 | 1]);
}

void push(int i, int l, int r) {
	if (!lazy[i]) return;
	it[i] += lazy[i];
	if (l != r) lazy[i << 1] += lazy[i], lazy[i << 1 | 1] += lazy[i];
	lazy[i] = 0; return;
}

void upd(int i, int l, int r, int L, int R) {
	push(i, l, r);
	if (l > R || L > r) return;
	if (L <= l && r <= R) {
		lazy[i] = 1, push(i, l, r); return;
	}
	int mid = (l + r) >> 1;
	upd(i << 1, l, mid, L, R);
	upd(i << 1 | 1, mid + 1, r, L, R);
	it[i] = min(it[i << 1], it[i << 1 | 1]);
}

int get(int i, int l, int r, int L, int R) {
	push(i, l, r);
	if (l > R || L > r) return INF;
	if (L <= l && r <= R) return it[i];
	int mid = (l + r) >> 1;
	return min(get(i << 1, l, mid, L, R), get(i << 1 | 1, mid + 1, r, L, R));
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> a[i], val.push_back(a[i]);
	sort(val.begin(), val.end()); val.erase(unique(val.begin(), val.end()), val.end());
	int sz = val.size();
	build(1, 0, sz - 1);
	for (int i = 1; i <= n; ++i) {
		int pos = lower_bound(val.begin(), val.end(), a[i]) - val.begin();
		res += get(1, 0, sz - 1, pos, sz - 1) - a[i];
		upd(1, 0, sz - 1, 0, pos - 1);
	}
	cout << res;
}
### 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 N = 200005;
const int INF = 1e9;

int n, a[N];
int lazy[4 * N], it[4 * N];
long long res;
vector<int> val;

void build(int i, int l, int r) {
	if (l == r) {
		it[i] = val[l]; return;
	}
	int mid = (l + r) >> 1;
	build(i << 1, l, mid), build(i << 1 | 1, mid + 1, r);
	it[i] = min(it[i << 1], it[i << 1 | 1]);
}

void push(int i, int l, int r) {
	if (!lazy[i]) return;
	it[i] += lazy[i];
	if (l != r) lazy[i << 1] += lazy[i], lazy[i << 1 | 1] += lazy[i];
	lazy[i] = 0; return;
}

void upd(int i, int l, int r, int L, int R) {
	push(i, l, r);
	if (l > R || L > r) return;
	if (L <= l && r <= R) {
		lazy[i] = 1, push(i, l, r); return;
	}
	int mid = (l + r) >> 1;
	upd(i << 1, l, mid, L, R);
	upd(i << 1 | 1, mid + 1, r, L, R);
	it[i] = min(it[i << 1], it[i << 1 | 1]);
}

int get(int i, int l, int r, int L, int R) {
	push(i, l, r);
	if (l > R || L > r) return INF;
	if (L <= l && r <= R) return it[i];
	int mid = (l + r) >> 1;
	return min(get(i << 1, l, mid, L, R), get(i << 1 | 1, mid + 1, r, L, R));
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> a[i], val.push_back(a[i]);
	sort(val.begin(), val.end()); val.erase(unique(val.begin(), val.end()), val.end());
	int sz = val.size();
	build(1, 0, sz - 1);
	for (int i = 1; i <= n; ++i) {
		int pos = lower_bound(val.begin(), val.end(), a[i]) - val.begin();
		res += get(1, 0, sz - 1, pos, sz - 1) - a[i];
		upd(1, 0, sz - 1, 0, pos - 1);
	}
	cout << res;
}
```