//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int inf=2e9;
const int MAXN=2e5+10;
int n,a[MAXN],b[MAXN],tot;
struct Segtree
{
	struct node
	{
		int tag,mi;
	}Tree[MAXN<<2];
#define root Tree[o]
#define lson Tree[o<<1]
#define rson Tree[o<<1|1]
	void pushup(int o)
	{
		root.mi=min(lson.mi,rson.mi);
	}
	void modify(int o,int c)
	{
		root.tag+=c;
		root.mi+=c;
	}
	void pushdown(int o)
	{
		if(root.tag)
		{
			modify(o<<1,root.tag);
			modify(o<<1|1,root.tag);
			root.tag=0;
		}
	}
	void BuildTree(int o,int l,int r)
	{
		root.tag=0;
		if(l==r)
			return (void)(root.mi=b[l]);
		int mid=(l+r)>>1;
		BuildTree(o<<1,l,mid);
		BuildTree(o<<1|1,mid+1,r);
		pushup(o);
	}
	void upd(int o,int l,int r,int L,int R,int c)
	{
		if(L<=l && r<=R)
			return modify(o,c);
		int mid=(l+r)>>1;
		pushdown(o);
		if(L<=mid)
			upd(o<<1,l,mid,L,R,c);
		if(R>mid)
			upd(o<<1|1,mid+1,r,L,R,c);
		pushup(o);
	}
	int query(int o,int l,int r,int L,int R)
	{
		if(L<=l && r<=R)
			return root.mi;
		int res=inf;
		int mid=(l+r)>>1;	
		pushdown(o);
		if(L<=mid)
			res=min(res,query(o<<1,l,mid,L,R));
		if(R>mid)
			res=min(res,query(o<<1|1,mid+1,r,L,R));
		return res;
	}
}T;
int main()
{
	n=read();
	for(int i=1;i<=n;++i)
		a[i]=b[i]=read();
	sort(b+1,b+1+n);
	tot=unique(b+1,b+1+n)-b-1;
	T.BuildTree(1,1,tot);
	ll ans=0;
	for(int i=1;i<=n;++i)
	{
		int x=lower_bound(b+1,b+1+tot,a[i])-b;
		ans+=T.query(1,1,tot,x,tot)-a[i];
		if(x>1)
			T.upd(1,1,tot,1,x-1,1);
	}
	cout<<ans<<endl;
	return 0;
}

### Prompt

Please create a solution in cpp 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
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int inf=2e9;
const int MAXN=2e5+10;
int n,a[MAXN],b[MAXN],tot;
struct Segtree
{
	struct node
	{
		int tag,mi;
	}Tree[MAXN<<2];
#define root Tree[o]
#define lson Tree[o<<1]
#define rson Tree[o<<1|1]
	void pushup(int o)
	{
		root.mi=min(lson.mi,rson.mi);
	}
	void modify(int o,int c)
	{
		root.tag+=c;
		root.mi+=c;
	}
	void pushdown(int o)
	{
		if(root.tag)
		{
			modify(o<<1,root.tag);
			modify(o<<1|1,root.tag);
			root.tag=0;
		}
	}
	void BuildTree(int o,int l,int r)
	{
		root.tag=0;
		if(l==r)
			return (void)(root.mi=b[l]);
		int mid=(l+r)>>1;
		BuildTree(o<<1,l,mid);
		BuildTree(o<<1|1,mid+1,r);
		pushup(o);
	}
	void upd(int o,int l,int r,int L,int R,int c)
	{
		if(L<=l && r<=R)
			return modify(o,c);
		int mid=(l+r)>>1;
		pushdown(o);
		if(L<=mid)
			upd(o<<1,l,mid,L,R,c);
		if(R>mid)
			upd(o<<1|1,mid+1,r,L,R,c);
		pushup(o);
	}
	int query(int o,int l,int r,int L,int R)
	{
		if(L<=l && r<=R)
			return root.mi;
		int res=inf;
		int mid=(l+r)>>1;	
		pushdown(o);
		if(L<=mid)
			res=min(res,query(o<<1,l,mid,L,R));
		if(R>mid)
			res=min(res,query(o<<1|1,mid+1,r,L,R));
		return res;
	}
}T;
int main()
{
	n=read();
	for(int i=1;i<=n;++i)
		a[i]=b[i]=read();
	sort(b+1,b+1+n);
	tot=unique(b+1,b+1+n)-b-1;
	T.BuildTree(1,1,tot);
	ll ans=0;
	for(int i=1;i<=n;++i)
	{
		int x=lower_bound(b+1,b+1+tot,a[i])-b;
		ans+=T.query(1,1,tot,x,tot)-a[i];
		if(x>1)
			T.upd(1,1,tot,1,x-1,1);
	}
	cout<<ans<<endl;
	return 0;
}

```