#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int inf=2e9;
int n,num;
int a[202020],b[202020],v[202020];
map<int,int> mp;
ll ans;
struct Segment_Tree
{
	int minn[2020202],addv[2020202];
	void down(int p)
	{
		if (addv[p])
		{
			minn[p]+=addv[p];
			addv[p*2]+=addv[p];
			addv[p*2+1]+=addv[p];
			addv[p]=0;
		}
	}
	void build(int p,int l,int r)
	{
		if (l==r)
		{
			minn[p]=v[l];
			return;
		}
		int mid=(l+r)/2;
		build(p*2,l,mid); build(p*2+1,mid+1,r);
		minn[p]=min(minn[p*2],minn[p*2+1]);
	}
	void add(int p,int l,int r,int x,int y,int V)
	{
		if (x>y) return;
		down(p);
		if (x<=l && r<=y)
		{
			addv[p]+=V;
			return;
		}
		int mid=(l+r)/2;
		if (x<=mid) add(p*2,l,mid,x,y,V);
		if (y>mid) add(p*2+1,mid+1,r,x,y,V);

		down(p*2); down(p*2+1);
		minn[p]=min(minn[p*2],minn[p*2+1]);
	}
	int find(int p,int l,int r,int x,int y)
	{
		down(p);
		if (x<=l && r<=y) return minn[p];
		int mid=(l+r)/2,sss=inf;
		if (x<=mid) sss=min(sss,find(p*2,l,mid,x,y));
		if (y>mid) sss=min(sss,find(p*2+1,mid+1,r,x,y));
		return sss;
	}
}S;
void init()
{
	for (int i=1;i<=n;++i) b[i]=a[i];
	sort(b+1,b+1+n);
	for (int i=1;i<=n;++i) if (b[i]!=b[i-1])
	{
		++num;
		v[num]=b[i]; mp[b[i]]=num;
	}
	S.build(1,1,num);
	for (int i=1;i<=n;++i) 
		S.add(1,1,num,1,mp[a[i]]-1,1);
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;++i) scanf("%d",&a[i]);
	init();
	for (int i=n;i>=1;--i)
	{
		S.add(1,1,num,1,mp[a[i]]-1,-1);
		ans+=(S.find(1,1,num,mp[a[i]],num) - a[i]);
	}
	printf("%lld\n",ans);
	return 0;
}
### Prompt

Please provide a CPP coded solution 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>
#define ll long long
using namespace std;
const int inf=2e9;
int n,num;
int a[202020],b[202020],v[202020];
map<int,int> mp;
ll ans;
struct Segment_Tree
{
	int minn[2020202],addv[2020202];
	void down(int p)
	{
		if (addv[p])
		{
			minn[p]+=addv[p];
			addv[p*2]+=addv[p];
			addv[p*2+1]+=addv[p];
			addv[p]=0;
		}
	}
	void build(int p,int l,int r)
	{
		if (l==r)
		{
			minn[p]=v[l];
			return;
		}
		int mid=(l+r)/2;
		build(p*2,l,mid); build(p*2+1,mid+1,r);
		minn[p]=min(minn[p*2],minn[p*2+1]);
	}
	void add(int p,int l,int r,int x,int y,int V)
	{
		if (x>y) return;
		down(p);
		if (x<=l && r<=y)
		{
			addv[p]+=V;
			return;
		}
		int mid=(l+r)/2;
		if (x<=mid) add(p*2,l,mid,x,y,V);
		if (y>mid) add(p*2+1,mid+1,r,x,y,V);

		down(p*2); down(p*2+1);
		minn[p]=min(minn[p*2],minn[p*2+1]);
	}
	int find(int p,int l,int r,int x,int y)
	{
		down(p);
		if (x<=l && r<=y) return minn[p];
		int mid=(l+r)/2,sss=inf;
		if (x<=mid) sss=min(sss,find(p*2,l,mid,x,y));
		if (y>mid) sss=min(sss,find(p*2+1,mid+1,r,x,y));
		return sss;
	}
}S;
void init()
{
	for (int i=1;i<=n;++i) b[i]=a[i];
	sort(b+1,b+1+n);
	for (int i=1;i<=n;++i) if (b[i]!=b[i-1])
	{
		++num;
		v[num]=b[i]; mp[b[i]]=num;
	}
	S.build(1,1,num);
	for (int i=1;i<=n;++i) 
		S.add(1,1,num,1,mp[a[i]]-1,1);
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;++i) scanf("%d",&a[i]);
	init();
	for (int i=n;i>=1;--i)
	{
		S.add(1,1,num,1,mp[a[i]]-1,-1);
		ans+=(S.find(1,1,num,mp[a[i]],num) - a[i]);
	}
	printf("%lld\n",ans);
	return 0;
}
```