#include <algorithm>
#include <utility>
#include <cstdio>
int arr[200005], app[200005], lazy[800005]; 
std::pair<int, int> seg[800005];
inline void paint(int u, int x)
{
	seg[u].first += x; 
	lazy[u] += x; 
}
inline void push_down(int u)
{
	if (lazy[u])
	{
		paint(u << 1, lazy[u]);
		paint(u << 1 | 1, lazy[u]); 
		lazy[u] = 0; 
	}
}
void build(int u, int l, int r)
{
	if (l == r)
	{
		seg[u] = {app[l], l}; 
		return; 
	}
	int m = l + r >> 1; 
	build(u << 1, l, m); 
	build(u << 1 | 1, m + 1, r); 
	seg[u] = std::min(seg[u << 1], seg[u << 1 | 1]); 
}
void modify(int u, int l, int r, int L, int R)
{
	if (L > R)
		return; 
	if (L <= l && r <= R)
	{
		paint(u, 1);
		return; 
	}
	push_down(u); 
	int m = l + r >> 1; 
	if (L <= m)
		modify(u << 1, l, m, L, R); 
	if (m < R)
		modify(u << 1 | 1, m + 1, r, L, R); 
	seg[u] = std::min(seg[u << 1], seg[u << 1 | 1]); 
}
std::pair<int, int> query(int u, int l, int r, int L, int R)
{
	if (L <= l && r <= R)
		return seg[u];
	push_down(u); 
	int m = l + r >> 1;
	if (R <= m)
		return query(u << 1, l, m, L, R); 
	if (m < L)
		return query(u << 1 | 1, m + 1, r, L, R); 
	return std::min(query(u << 1, l, m, L, R), query(u << 1 | 1, m + 1, r, L, R)); 
}
int main()
{
	// freopen("CF17-EX-B.in", "r", stdin); 
	int n;
	scanf("%d", &n); 
	for (int i = 0; i < n; i++)
	{
		scanf("%d", arr + i);
		app[i] = arr[i]; 
	}
	std::sort(app, app + n); 
	build(1, 0, n - 1); 
	long long ans = 0; 
	for (int i = 0; i < n; i++)
	{
		int pos = std::lower_bound(app, app + n, arr[i]) - app; 
		auto res = query(1, 0, n - 1, pos, n - 1); 
		ans += res.first - arr[i]; 
		modify(1, 0, n - 1, 0, res.second - 1); 
	}
	printf("%lld\n", ans);
	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 <algorithm>
#include <utility>
#include <cstdio>
int arr[200005], app[200005], lazy[800005]; 
std::pair<int, int> seg[800005];
inline void paint(int u, int x)
{
	seg[u].first += x; 
	lazy[u] += x; 
}
inline void push_down(int u)
{
	if (lazy[u])
	{
		paint(u << 1, lazy[u]);
		paint(u << 1 | 1, lazy[u]); 
		lazy[u] = 0; 
	}
}
void build(int u, int l, int r)
{
	if (l == r)
	{
		seg[u] = {app[l], l}; 
		return; 
	}
	int m = l + r >> 1; 
	build(u << 1, l, m); 
	build(u << 1 | 1, m + 1, r); 
	seg[u] = std::min(seg[u << 1], seg[u << 1 | 1]); 
}
void modify(int u, int l, int r, int L, int R)
{
	if (L > R)
		return; 
	if (L <= l && r <= R)
	{
		paint(u, 1);
		return; 
	}
	push_down(u); 
	int m = l + r >> 1; 
	if (L <= m)
		modify(u << 1, l, m, L, R); 
	if (m < R)
		modify(u << 1 | 1, m + 1, r, L, R); 
	seg[u] = std::min(seg[u << 1], seg[u << 1 | 1]); 
}
std::pair<int, int> query(int u, int l, int r, int L, int R)
{
	if (L <= l && r <= R)
		return seg[u];
	push_down(u); 
	int m = l + r >> 1;
	if (R <= m)
		return query(u << 1, l, m, L, R); 
	if (m < L)
		return query(u << 1 | 1, m + 1, r, L, R); 
	return std::min(query(u << 1, l, m, L, R), query(u << 1 | 1, m + 1, r, L, R)); 
}
int main()
{
	// freopen("CF17-EX-B.in", "r", stdin); 
	int n;
	scanf("%d", &n); 
	for (int i = 0; i < n; i++)
	{
		scanf("%d", arr + i);
		app[i] = arr[i]; 
	}
	std::sort(app, app + n); 
	build(1, 0, n - 1); 
	long long ans = 0; 
	for (int i = 0; i < n; i++)
	{
		int pos = std::lower_bound(app, app + n, arr[i]) - app; 
		auto res = query(1, 0, n - 1, pos, n - 1); 
		ans += res.first - arr[i]; 
		modify(1, 0, n - 1, 0, res.second - 1); 
	}
	printf("%lld\n", ans);
	return 0; 
}

```