#include<cstdio>
#include<algorithm>
using namespace std;
#define INF ((1<<30) - 1)
int n;
struct Tree {
	Tree *c1, *c2;
	int L, S, pv;
	Tree(int b, int e) {
		L = 0;
		c1 = c2 = NULL;
		pv = b - 1;
		S = -1 * (e - b + 1);
	}
	Tree GetMax(int b, int e, int s) {
		if (b == s)return *this;
		int m = (b + e) >> 1;
		if (!c1) {
			c1 = new Tree(b, m);
			c2 = new Tree(m + 1, e);
		}
		if (m < s) return c2->GetMax(m + 1, e, s);
		Tree ret = c1->GetMax(b, m, s);
		if (ret.L < ret.S + c2->L) {
			ret.L = ret.S + c2->L;
			ret.pv = c2->pv;
		}
		ret.S = ret.S + c2->S;
		return ret;
	}
	void Add(int b, int e, int x) {
		if (b == e) {
			S++;
			if (S > 0) {
				L = S;
				pv = b;
			}
			return;
		}
		int m = (b + e) >> 1;
		if (c1 == NULL) {
			c1 = new Tree(b, m);
			c2 = new Tree(m + 1, e);
		}
		if (x <= m)c1->Add(b, m, x);
		else c2->Add(m + 1, e, x);
		S = c1->S + c2->S;
		L = max(c1->L, c1->S + c2->L);
		pv = c1->pv;
		if (L != c1->L) pv = c2->pv;
	}
	int Sum(int b, int e, int x) {
		if (b == x)return S;
		int m = (b + e) >> 1, r = 0;
		if (!c1) {
			c1 = new Tree(b, m);
			c2 = new Tree(m+1, e);
		}
		if (x <= m) {
			r = c2->S + c1->Sum(b, m, x);
		}
		else {
			r = c2->Sum(m + 1, e, x);
		}
		return r;
	}
};
int main() {
	int i, a;
	scanf("%d", &n);
	long long res = 0, SS = 0;
	Tree *Root = new Tree(0, INF);
	for (i = 1; i <= n; i++) {
		scanf("%d", &a);
		Tree rr = Root->GetMax(0, INF, a+1);
		res += rr.pv - a;
		res += Root->Sum(0, INF, rr.pv + 1) + (INF - rr.pv);
		Root->Add(0, INF, rr.pv);
		SS += rr.pv - a;
	}
	printf("%lld\n", res);
}
### Prompt

Your challenge is to write 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<cstdio>
#include<algorithm>
using namespace std;
#define INF ((1<<30) - 1)
int n;
struct Tree {
	Tree *c1, *c2;
	int L, S, pv;
	Tree(int b, int e) {
		L = 0;
		c1 = c2 = NULL;
		pv = b - 1;
		S = -1 * (e - b + 1);
	}
	Tree GetMax(int b, int e, int s) {
		if (b == s)return *this;
		int m = (b + e) >> 1;
		if (!c1) {
			c1 = new Tree(b, m);
			c2 = new Tree(m + 1, e);
		}
		if (m < s) return c2->GetMax(m + 1, e, s);
		Tree ret = c1->GetMax(b, m, s);
		if (ret.L < ret.S + c2->L) {
			ret.L = ret.S + c2->L;
			ret.pv = c2->pv;
		}
		ret.S = ret.S + c2->S;
		return ret;
	}
	void Add(int b, int e, int x) {
		if (b == e) {
			S++;
			if (S > 0) {
				L = S;
				pv = b;
			}
			return;
		}
		int m = (b + e) >> 1;
		if (c1 == NULL) {
			c1 = new Tree(b, m);
			c2 = new Tree(m + 1, e);
		}
		if (x <= m)c1->Add(b, m, x);
		else c2->Add(m + 1, e, x);
		S = c1->S + c2->S;
		L = max(c1->L, c1->S + c2->L);
		pv = c1->pv;
		if (L != c1->L) pv = c2->pv;
	}
	int Sum(int b, int e, int x) {
		if (b == x)return S;
		int m = (b + e) >> 1, r = 0;
		if (!c1) {
			c1 = new Tree(b, m);
			c2 = new Tree(m+1, e);
		}
		if (x <= m) {
			r = c2->S + c1->Sum(b, m, x);
		}
		else {
			r = c2->Sum(m + 1, e, x);
		}
		return r;
	}
};
int main() {
	int i, a;
	scanf("%d", &n);
	long long res = 0, SS = 0;
	Tree *Root = new Tree(0, INF);
	for (i = 1; i <= n; i++) {
		scanf("%d", &a);
		Tree rr = Root->GetMax(0, INF, a+1);
		res += rr.pv - a;
		res += Root->Sum(0, INF, rr.pv + 1) + (INF - rr.pv);
		Root->Add(0, INF, rr.pv);
		SS += rr.pv - a;
	}
	printf("%lld\n", res);
}
```