#include <bits/stdc++.h>
#define xx first
#define yy second
#define mp make_pair
#define pb push_back
#define mset(x, y) memset(x, y, sizeof x)
#define mcpy(x, y) memcpy(x, y, sizeof x)
using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

inline int Read()
{
	int x = 0, f = 1, c = getchar();
	for (; !isdigit(c); c = getchar())
		if (c == '-')
			f = -1;
	for (;  isdigit(c); c = getchar())
		x = x * 10 + c - '0';
	return x * f;
}

const int MAXN = 200005;

int n, m, a[MAXN], b[MAXN], tag[MAXN << 2];
pii val[MAXN << 2];
LL ans;

inline void Build(int x, int l, int r)
{
	val[x] = mp(b[l], l);
	if (l == r)
		return ;
	int mid = l + r >> 1;
	Build(x << 1, l, mid), Build(x << 1 | 1, mid + 1, r);
}

inline void Modify(int x, int l, int r, int ql, int qr)
{
	if (l == ql && r == qr)
		return (void)(val[x].xx ++, tag[x] ++);
	if (tag[x])
		val[x << 1].xx += tag[x], tag[x << 1] += tag[x], val[x << 1 | 1].xx += tag[x], tag[x << 1 | 1] += tag[x], tag[x] = 0;
	int mid = l + r >> 1;
	if (qr <= mid)
		Modify(x << 1, l, mid, ql, qr);
	else if (ql > mid)
		Modify(x << 1 | 1, mid + 1, r, ql, qr);
	else
		Modify(x << 1, l, mid, ql, mid), Modify(x << 1 | 1, mid + 1, r, mid + 1, qr);
	val[x] = min(val[x << 1], val[x << 1 | 1]);
}

inline pii Query(int x, int l, int r, int ql, int qr)
{
	if (l == ql && r == qr)
		return val[x];
	if (tag[x])
		val[x << 1].xx += tag[x], tag[x << 1] += tag[x], val[x << 1 | 1].xx += tag[x], tag[x << 1 | 1] += tag[x], tag[x] = 0;
	int mid = l + r >> 1;
	if (qr <= mid)
		return Query(x << 1, l, mid, ql, qr);
	if (ql > mid)
		return Query(x << 1 | 1, mid + 1, r, ql, qr);
	return min(Query(x << 1, l, mid, ql, mid), Query(x << 1 | 1, mid + 1, r, mid + 1, qr));
}

int main()
{
#ifdef wxh010910
	freopen("data.in", "r", stdin);
#endif
	n = Read();
	for (int i = 1; i <= n; i ++)
		a[i] = b[i] = Read(), ans -= a[i];
	sort(b + 1, b + n + 1), m = unique(b + 1, b + n + 1) - b - 1, Build(1, 1, m);
	for (int i = 1; i <= n; i ++)
	{
		pii val = Query(1, 1, m, lower_bound(b + 1, b + m + 1, a[i]) - b, m);
		ans += val.xx;
		if (val.yy > 1)
			Modify(1, 1, m, 1, val.yy - 1);
	}
	return printf("%lld\n", ans), 0;
}

### Prompt

Your task is to create a CPP solution to 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>
#define xx first
#define yy second
#define mp make_pair
#define pb push_back
#define mset(x, y) memset(x, y, sizeof x)
#define mcpy(x, y) memcpy(x, y, sizeof x)
using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

inline int Read()
{
	int x = 0, f = 1, c = getchar();
	for (; !isdigit(c); c = getchar())
		if (c == '-')
			f = -1;
	for (;  isdigit(c); c = getchar())
		x = x * 10 + c - '0';
	return x * f;
}

const int MAXN = 200005;

int n, m, a[MAXN], b[MAXN], tag[MAXN << 2];
pii val[MAXN << 2];
LL ans;

inline void Build(int x, int l, int r)
{
	val[x] = mp(b[l], l);
	if (l == r)
		return ;
	int mid = l + r >> 1;
	Build(x << 1, l, mid), Build(x << 1 | 1, mid + 1, r);
}

inline void Modify(int x, int l, int r, int ql, int qr)
{
	if (l == ql && r == qr)
		return (void)(val[x].xx ++, tag[x] ++);
	if (tag[x])
		val[x << 1].xx += tag[x], tag[x << 1] += tag[x], val[x << 1 | 1].xx += tag[x], tag[x << 1 | 1] += tag[x], tag[x] = 0;
	int mid = l + r >> 1;
	if (qr <= mid)
		Modify(x << 1, l, mid, ql, qr);
	else if (ql > mid)
		Modify(x << 1 | 1, mid + 1, r, ql, qr);
	else
		Modify(x << 1, l, mid, ql, mid), Modify(x << 1 | 1, mid + 1, r, mid + 1, qr);
	val[x] = min(val[x << 1], val[x << 1 | 1]);
}

inline pii Query(int x, int l, int r, int ql, int qr)
{
	if (l == ql && r == qr)
		return val[x];
	if (tag[x])
		val[x << 1].xx += tag[x], tag[x << 1] += tag[x], val[x << 1 | 1].xx += tag[x], tag[x << 1 | 1] += tag[x], tag[x] = 0;
	int mid = l + r >> 1;
	if (qr <= mid)
		return Query(x << 1, l, mid, ql, qr);
	if (ql > mid)
		return Query(x << 1 | 1, mid + 1, r, ql, qr);
	return min(Query(x << 1, l, mid, ql, mid), Query(x << 1 | 1, mid + 1, r, mid + 1, qr));
}

int main()
{
#ifdef wxh010910
	freopen("data.in", "r", stdin);
#endif
	n = Read();
	for (int i = 1; i <= n; i ++)
		a[i] = b[i] = Read(), ans -= a[i];
	sort(b + 1, b + n + 1), m = unique(b + 1, b + n + 1) - b - 1, Build(1, 1, m);
	for (int i = 1; i <= n; i ++)
	{
		pii val = Query(1, 1, m, lower_bound(b + 1, b + m + 1, a[i]) - b, m);
		ans += val.xx;
		if (val.yy > 1)
			Modify(1, 1, m, 1, val.yy - 1);
	}
	return printf("%lld\n", ans), 0;
}

```