#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
const int MAXN = 200005;
const int MAXT = 530000;

int n, a[MAXN];
vector<int> v;

struct seg{
	pi  tree[MAXT];
	int lazy[MAXT];
	void init(int s, int e, int p, vector<int> &v){
		if(s == e){
			tree[p] = pi(v[s], s);
			return;
		}
		int m = (s + e) / 2;
		init(s, m, 2*p, v);
		init(m+1, e, 2*p+1, v);
		tree[p] = min(tree[2*p], tree[2*p+1]);
	}
	void lazydown(int p){
		tree[2*p].first += lazy[p];
		tree[2*p+1].first += lazy[p];
		lazy[2*p] += lazy[p];
		lazy[2*p+1] += lazy[p];
		lazy[p] = 0;
	}
	void add(int s, int e, int ps, int pe, int p, int v){
		if(e < ps || pe < s) return;
		if(s <= ps && pe <= e){
			tree[p].first += v;
			lazy[p] += v;
			return;
		}
		int pm = (ps + pe) / 2;
		lazydown(p);
		add(s, e, ps, pm, 2*p, v);
		add(s, e, pm+1, pe, 2*p+1, v);
		tree[p] = min(tree[2*p], tree[2*p+1]);
	}
	pi query(int s, int e, int ps, int pe, int p){
		if(e < ps || pe < s) return pi(2e9, -1);
		if(s <= ps && pe <= e) return tree[p];
		int pm = (ps + pe) / 2;
		lazydown(p);
		return min(query(s, e, ps, pm, 2*p), query(s, e, pm+1, pe, 2*p+1));
	}
}seg;

int main(){
	scanf("%d",&n);
	for(int i=0; i<n; i++){
		scanf("%d",&a[i]);
		v.push_back(a[i]);
	}
	sort(v.begin(), v.end());
	v.resize(unique(v.begin(), v.end()) - v.begin());
	seg.init(0, v.size() - 1, 1, v);
	lint ans = 0;
	for(int i=0; i<n; i++){
		a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
		auto ret = seg.query(a[i], v.size() - 1, 0, v.size() - 1, 1);
		ans += ret.first - v[a[i]];
		seg.add(0, ret.second - 1, 0, v.size() - 1, 1, 1);
	}
	cout << ans << endl;
}

### 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 <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
const int MAXN = 200005;
const int MAXT = 530000;

int n, a[MAXN];
vector<int> v;

struct seg{
	pi  tree[MAXT];
	int lazy[MAXT];
	void init(int s, int e, int p, vector<int> &v){
		if(s == e){
			tree[p] = pi(v[s], s);
			return;
		}
		int m = (s + e) / 2;
		init(s, m, 2*p, v);
		init(m+1, e, 2*p+1, v);
		tree[p] = min(tree[2*p], tree[2*p+1]);
	}
	void lazydown(int p){
		tree[2*p].first += lazy[p];
		tree[2*p+1].first += lazy[p];
		lazy[2*p] += lazy[p];
		lazy[2*p+1] += lazy[p];
		lazy[p] = 0;
	}
	void add(int s, int e, int ps, int pe, int p, int v){
		if(e < ps || pe < s) return;
		if(s <= ps && pe <= e){
			tree[p].first += v;
			lazy[p] += v;
			return;
		}
		int pm = (ps + pe) / 2;
		lazydown(p);
		add(s, e, ps, pm, 2*p, v);
		add(s, e, pm+1, pe, 2*p+1, v);
		tree[p] = min(tree[2*p], tree[2*p+1]);
	}
	pi query(int s, int e, int ps, int pe, int p){
		if(e < ps || pe < s) return pi(2e9, -1);
		if(s <= ps && pe <= e) return tree[p];
		int pm = (ps + pe) / 2;
		lazydown(p);
		return min(query(s, e, ps, pm, 2*p), query(s, e, pm+1, pe, 2*p+1));
	}
}seg;

int main(){
	scanf("%d",&n);
	for(int i=0; i<n; i++){
		scanf("%d",&a[i]);
		v.push_back(a[i]);
	}
	sort(v.begin(), v.end());
	v.resize(unique(v.begin(), v.end()) - v.begin());
	seg.init(0, v.size() - 1, 1, v);
	lint ans = 0;
	for(int i=0; i<n; i++){
		a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
		auto ret = seg.query(a[i], v.size() - 1, 0, v.size() - 1, 1);
		ans += ret.first - v[a[i]];
		seg.add(0, ret.second - 1, 0, v.size() - 1, 1, 1);
	}
	cout << ans << endl;
}

```