#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> Pi;
typedef long long ll;
#define pii Pi
#define pll PL
#define Fi first
#define Se second
#define pb(x) push_back(x)
//#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> pll;
typedef long double ldouble;
typedef pair<double, double> pdd;

const double PI = acos(-1);
const double EPS = 1e-9;

const int MX = 1<<20;
const int MM = 1000000007;

struct Tree{
	struct node{
		pii v;
		int add;
	};
	node t[MX*2];
	void update(int l, int r, int v, int n = 1, int s = 0, int e = MX-1){
		if( r < s || e < l ) return;
		else if( l <= s && e <= r ){
			t[n].v.first += v;
			t[n].add += v;
		}
		else{
			int m = (s+e) / 2;
			update(l, r, v, n*2, s, m);
			update(l, r, v, n*2+1, m+1, e);
			t[n].v = min(t[n*2].v, t[n*2+1].v);
			t[n].v.first += t[n].add;
		}
	}
	pii read(int l, int r, int n = 1, int s = 0, int e = MX-1){
		if( r < s || e < l ) return pii(1e9, -1);
		else if( l <= s && e <= r ) return t[n].v;
		else{
			int m = (s+e) / 2;
			pii res = min(read(l, r, n*2, s, m), read(l, r, n*2+1, m+1, e));
			res.first += t[n].add;
			return res;
		}
	}
} tree;

int A[MX];

int main()
{
	int N;
	vector<int> X;
	scanf("%d", &N);
	for(int i = 1; i <= N; i++) scanf("%d", A+i), X.push_back(A[i]);
	sort(X.begin(), X.end());
	X.erase(unique(X.begin(), X.end()), X.end());

	for(int i = 0; i < X.size(); i++) tree.t[i+MX].v = pii(X[i], i);
	for(int i = MX-1; i >= 1; i--) tree.t[i].v = min(tree.t[i*2].v, tree.t[i*2+1].v);

	ll ans = 0;
	for(int i = 1; i <= N; i++){
		int v = A[i], w = lower_bound(X.begin(), X.end(), A[i]) - X.begin();
		pii t = tree.read(w, X.size()-1);
		ans += t.first - v;
		tree.update(0, t.second-1, 1);
	}
	printf("%lld\n", ans);
}

### Prompt

In CPP, your task is to solve 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 <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> Pi;
typedef long long ll;
#define pii Pi
#define pll PL
#define Fi first
#define Se second
#define pb(x) push_back(x)
//#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> pll;
typedef long double ldouble;
typedef pair<double, double> pdd;

const double PI = acos(-1);
const double EPS = 1e-9;

const int MX = 1<<20;
const int MM = 1000000007;

struct Tree{
	struct node{
		pii v;
		int add;
	};
	node t[MX*2];
	void update(int l, int r, int v, int n = 1, int s = 0, int e = MX-1){
		if( r < s || e < l ) return;
		else if( l <= s && e <= r ){
			t[n].v.first += v;
			t[n].add += v;
		}
		else{
			int m = (s+e) / 2;
			update(l, r, v, n*2, s, m);
			update(l, r, v, n*2+1, m+1, e);
			t[n].v = min(t[n*2].v, t[n*2+1].v);
			t[n].v.first += t[n].add;
		}
	}
	pii read(int l, int r, int n = 1, int s = 0, int e = MX-1){
		if( r < s || e < l ) return pii(1e9, -1);
		else if( l <= s && e <= r ) return t[n].v;
		else{
			int m = (s+e) / 2;
			pii res = min(read(l, r, n*2, s, m), read(l, r, n*2+1, m+1, e));
			res.first += t[n].add;
			return res;
		}
	}
} tree;

int A[MX];

int main()
{
	int N;
	vector<int> X;
	scanf("%d", &N);
	for(int i = 1; i <= N; i++) scanf("%d", A+i), X.push_back(A[i]);
	sort(X.begin(), X.end());
	X.erase(unique(X.begin(), X.end()), X.end());

	for(int i = 0; i < X.size(); i++) tree.t[i+MX].v = pii(X[i], i);
	for(int i = MX-1; i >= 1; i--) tree.t[i].v = min(tree.t[i*2].v, tree.t[i*2+1].v);

	ll ans = 0;
	for(int i = 1; i <= N; i++){
		int v = A[i], w = lower_bound(X.begin(), X.end(), A[i]) - X.begin();
		pii t = tree.read(w, X.size()-1);
		ans += t.first - v;
		tree.update(0, t.second-1, 1);
	}
	printf("%lld\n", ans);
}

```