#ifndef LOCAL
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

typedef long long ll;
typedef long long llong;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;

/*
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
*/

vector<int> vv;
int a[220000];
int n;
int fv[220000];

int get(int x) {
	int ans = 0;
	for (; x >= 0; x = ((x & (x + 1)) - 1))
		ans += fv[x];
	return ans;
}

void add(int x) {
	for (; x < vv.size(); x |= (x + 1))
		fv[x] += 1;
}
const ll INF = 1e18;

pair<ll, int> rmq[220000 * 4];
ll dd[220000 * 4];

void build(int v, int tl, int tr) {
	if (tl + 1 == tr) {
		rmq[v] = make_pair(0, tl);
		return;
	}
	int m = (tl + tr) >> 1;
	build(v * 2 + 1, tl, m);
	build(v * 2 + 2, m, tr);
	rmq[v] = max(rmq[v * 2 + 1], rmq[v * 2 + 2]);
}


void push(int v) {
	if (dd[v]) {
		dd[v * 2 + 1] += dd[v];
		rmq[v * 2 + 1].first += dd[v];
		dd[v * 2 + 2] += dd[v];
		rmq[v * 2 + 2].first += dd[v];
		dd[v] = 0;
	}
}

void add(int v, int tl, int tr, int l, int r, int d) {
	if (r <= tl || tr <= l)
		return;
	if (l <= tl && tr <= r) {
		rmq[v].first += d;
		dd[v] += d;
		return;
	}
	push(v);
	int m = (tl + tr) >> 1;
	add(v * 2 + 1, tl, m, l, r, d);
	add(v * 2 + 2, m, tr, l, r, d);
	rmq[v] = max(rmq[v * 2 + 1], rmq[v * 2 + 2]);
}

pair<ll, int> get(int v, int tl, int tr, int l, int r) {
	if (r <= tl || tr <= l)
		return make_pair(-INF, 0);
	if (l <= tl && tr <= r)
		return rmq[v];
	push(v);
	int m = (tl + tr) >> 1;
	return max(get(v * 2 + 1, tl, m, l, r), get(v * 2 + 2, m, tr, l, r));
}

int main() {
	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> a[i], vv.push_back(a[i]);
	sort(vv.begin(), vv.end());
	vv.resize(unique(vv.begin(), vv.end()) - vv.begin());
	build(0, 0, vv.size());
	for (int i = 0; i < vv.size(); ++i)
		add(0, 0, vv.size(), i, i + 1, -vv[i]);
	for (int i = 0; i < n; ++i) {
		int x = lower_bound(vv.begin(), vv.end(), a[i]) - vv.begin();
		add(0, 0, vv.size(), x, vv.size(), 1);
	}
	ll ans = 0;
	for (int i = n - 1; i >= 0; --i) {
		int x = lower_bound(vv.begin(), vv.end(), a[i]) - vv.begin();
		add(0, 0, vv.size(), x, vv.size(), -1);
		int go = get(0, 0, vv.size(), x, vv.size()).second;
		assert(go >= x);
		ans += vv[go] - a[i];
		a[i] = vv[go];
	}
	for (int i = 0; i < n; ++i)
		a[i] = lower_bound(vv.begin(), vv.end(), a[i]) - vv.begin();
	for (int i = n - 1; i >= 0; --i) {
		if (a[i] > 0)
			ans += get(a[i] - 1);
		add(a[i]);
	}
	cout << ans << "\n";
	return 0;
}



### Prompt

Create a solution in Cpp for 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
#ifndef LOCAL
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

typedef long long ll;
typedef long long llong;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;

/*
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
*/

vector<int> vv;
int a[220000];
int n;
int fv[220000];

int get(int x) {
	int ans = 0;
	for (; x >= 0; x = ((x & (x + 1)) - 1))
		ans += fv[x];
	return ans;
}

void add(int x) {
	for (; x < vv.size(); x |= (x + 1))
		fv[x] += 1;
}
const ll INF = 1e18;

pair<ll, int> rmq[220000 * 4];
ll dd[220000 * 4];

void build(int v, int tl, int tr) {
	if (tl + 1 == tr) {
		rmq[v] = make_pair(0, tl);
		return;
	}
	int m = (tl + tr) >> 1;
	build(v * 2 + 1, tl, m);
	build(v * 2 + 2, m, tr);
	rmq[v] = max(rmq[v * 2 + 1], rmq[v * 2 + 2]);
}


void push(int v) {
	if (dd[v]) {
		dd[v * 2 + 1] += dd[v];
		rmq[v * 2 + 1].first += dd[v];
		dd[v * 2 + 2] += dd[v];
		rmq[v * 2 + 2].first += dd[v];
		dd[v] = 0;
	}
}

void add(int v, int tl, int tr, int l, int r, int d) {
	if (r <= tl || tr <= l)
		return;
	if (l <= tl && tr <= r) {
		rmq[v].first += d;
		dd[v] += d;
		return;
	}
	push(v);
	int m = (tl + tr) >> 1;
	add(v * 2 + 1, tl, m, l, r, d);
	add(v * 2 + 2, m, tr, l, r, d);
	rmq[v] = max(rmq[v * 2 + 1], rmq[v * 2 + 2]);
}

pair<ll, int> get(int v, int tl, int tr, int l, int r) {
	if (r <= tl || tr <= l)
		return make_pair(-INF, 0);
	if (l <= tl && tr <= r)
		return rmq[v];
	push(v);
	int m = (tl + tr) >> 1;
	return max(get(v * 2 + 1, tl, m, l, r), get(v * 2 + 2, m, tr, l, r));
}

int main() {
	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> a[i], vv.push_back(a[i]);
	sort(vv.begin(), vv.end());
	vv.resize(unique(vv.begin(), vv.end()) - vv.begin());
	build(0, 0, vv.size());
	for (int i = 0; i < vv.size(); ++i)
		add(0, 0, vv.size(), i, i + 1, -vv[i]);
	for (int i = 0; i < n; ++i) {
		int x = lower_bound(vv.begin(), vv.end(), a[i]) - vv.begin();
		add(0, 0, vv.size(), x, vv.size(), 1);
	}
	ll ans = 0;
	for (int i = n - 1; i >= 0; --i) {
		int x = lower_bound(vv.begin(), vv.end(), a[i]) - vv.begin();
		add(0, 0, vv.size(), x, vv.size(), -1);
		int go = get(0, 0, vv.size(), x, vv.size()).second;
		assert(go >= x);
		ans += vv[go] - a[i];
		a[i] = vv[go];
	}
	for (int i = 0; i < n; ++i)
		a[i] = lower_bound(vv.begin(), vv.end(), a[i]) - vv.begin();
	for (int i = n - 1; i >= 0; --i) {
		if (a[i] > 0)
			ans += get(a[i] - 1);
		add(a[i]);
	}
	cout << ans << "\n";
	return 0;
}



```