// This amazing code is by Eric Sunli Chen.
#include<bits/stdc++.h>
using namespace std;
template<typename T> bool get_int(T &x)
{
	char t=getchar();
	bool neg=false;
	x=0;
	for(; (t>'9'||t<'0')&&t!='-'&&t!=EOF; t=getchar());
	if(t=='-')neg=true,t=getchar();if(t==EOF)return false;
	for(; t<='9'&&t>='0'; t=getchar())x=x*10+t-'0';
	if(neg)x=-x;return true;
}
template<typename T> void print_int(T x)
{
	if(x<0)putchar('-'),x=-x;
	short a[20]= {},sz=0;
	while(x>0)a[sz++]=x%10,x/=10;
	if(sz==0)putchar('0');
	for(int i=sz-1; i>=0; i--)putchar('0'+a[i]);
}
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define get1(a) get_int(a)
#define get2(a,b) (get1(a)&&get1(b))
#define get3(a,b,c) (get1(a)&&get2(b,c))
#define printendl(a) print_int(a),puts("")
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
const LL Linf=1ll<<61;
const double pi=acos(-1.0);

const int maxn=200111;
const int mod=1e9+7;
int qpow(int x,int y)
{
	int ret=1;
	while(y)
	{
		if(y&1)ret=(LL)ret*x%mod;
		x=(LL)x*x%mod;
		y>>=1;
	}
	return ret;
}

int bit[maxn];
void add(int x,int v)
{
	for(;x<maxn;x+=x&-x)
	{
		bit[x]+=v;
		if(bit[x]>=mod)bit[x]-=mod;
	}
}
int query(int x)
{
	int ret=0;
	for(;x;x-=x&-x)
	{
		ret+=bit[x];
		if(ret>=mod)ret-=mod;
	}
	return ret;
}
vector<pii>vs;
void roll_back()
{
	for(int i=0;i<(int)vs.size();i++)add(vs[i].ff,mod-vs[i].ss);
	vs.clear();
}

int n,inv[maxn],pre[maxn],suf[maxn];
pii p[maxn];


int main()
{
	get1(n);
	for(int i=1;i<=n;i++)
	{
		get1(p[i].ff);
		p[i].ss=i;
	}
	sort(p+1,p+n+1);
	
	for(int i=1;i<=n;i++)if(p[i].ff<i)
	{
		puts("0");
		return 0;
	}
	
	for(int i=1;i<=n;i++)inv[i]=qpow(i,mod-2);
	pre[0]=suf[n+1]=1;
	for(int i=1;i<=n;i++)pre[i]=(LL)pre[i-1]*(p[i].ff-i+1)%mod;
	for(int i=n;i>=1;i--)suf[i]=(LL)suf[i+1]*(p[i].ff-i+1)%mod;
	
	int cur=1,ans=0,cnt=0;
	for(int i=1;i<=n;i++)
	{
		int val1=query(n),val2=query(p[i].ss);val1-=val2;if(val1<0)val1+=mod;
		ans=(ans+(LL)(val2-val1+mod)*suf[i+1]%mod*cur)%mod;
		if(p[i].ff==i)
		{
			roll_back();
			cur=1;
		}
		else
		{
			int v=(LL)pre[i]*qpow(cur,mod-2)%mod;
			add(p[i].ss,v);
			vs.pb(mp(p[i].ss,v));
			cur=(LL)cur*(p[i].ff-i)%mod;
		}
	}
	if(ans&1)ans+=mod;ans>>=1;
	
	memset(bit,0,sizeof(bit));
	for(int i=1;i<=n;i++)
	{
		cnt+=i-1-query(p[i].ss);if(cnt>=mod)cnt-=mod;
		add(p[i].ss,1);
	}
	ans=(ans+(LL)pre[n]*cnt)%mod;
	printendl(ans);
	return 0;
}
### Prompt

Your task is to create a cpp solution to the following problem:

Snuke has an integer sequence A whose length is N. He likes permutations of (1, 2, ..., N), P, that satisfy the following condition:

* P_i \leq A_i for all i ( 1 \leq i \leq N ).



Snuke is interested in the inversion numbers of such permutations. Find the sum of the inversion numbers over all permutations that satisfy the condition. Since this can be extremely large, compute the sum modulo 10^9+7.

Constraints

* 1 \leq N \leq 2 \times 10^5
* 1 \leq A_i \leq N ( 1 \leq i \leq N )
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N
A_1 A_2 ... A_N


Output

Print the sum of the inversion numbers over all permutations that satisfy the condition.

Examples

Input

3
2 3 3


Output

4


Input

6
4 2 5 1 6 3


Output

7


Input

5
4 4 4 4 4


Output

0


Input

30
22 30 15 20 10 29 11 29 28 11 26 10 18 28 22 5 29 16 24 24 27 10 21 30 29 19 28 27 18 23


Output

848414012

### Response

```cpp
// This amazing code is by Eric Sunli Chen.
#include<bits/stdc++.h>
using namespace std;
template<typename T> bool get_int(T &x)
{
	char t=getchar();
	bool neg=false;
	x=0;
	for(; (t>'9'||t<'0')&&t!='-'&&t!=EOF; t=getchar());
	if(t=='-')neg=true,t=getchar();if(t==EOF)return false;
	for(; t<='9'&&t>='0'; t=getchar())x=x*10+t-'0';
	if(neg)x=-x;return true;
}
template<typename T> void print_int(T x)
{
	if(x<0)putchar('-'),x=-x;
	short a[20]= {},sz=0;
	while(x>0)a[sz++]=x%10,x/=10;
	if(sz==0)putchar('0');
	for(int i=sz-1; i>=0; i--)putchar('0'+a[i]);
}
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define get1(a) get_int(a)
#define get2(a,b) (get1(a)&&get1(b))
#define get3(a,b,c) (get1(a)&&get2(b,c))
#define printendl(a) print_int(a),puts("")
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
const LL Linf=1ll<<61;
const double pi=acos(-1.0);

const int maxn=200111;
const int mod=1e9+7;
int qpow(int x,int y)
{
	int ret=1;
	while(y)
	{
		if(y&1)ret=(LL)ret*x%mod;
		x=(LL)x*x%mod;
		y>>=1;
	}
	return ret;
}

int bit[maxn];
void add(int x,int v)
{
	for(;x<maxn;x+=x&-x)
	{
		bit[x]+=v;
		if(bit[x]>=mod)bit[x]-=mod;
	}
}
int query(int x)
{
	int ret=0;
	for(;x;x-=x&-x)
	{
		ret+=bit[x];
		if(ret>=mod)ret-=mod;
	}
	return ret;
}
vector<pii>vs;
void roll_back()
{
	for(int i=0;i<(int)vs.size();i++)add(vs[i].ff,mod-vs[i].ss);
	vs.clear();
}

int n,inv[maxn],pre[maxn],suf[maxn];
pii p[maxn];


int main()
{
	get1(n);
	for(int i=1;i<=n;i++)
	{
		get1(p[i].ff);
		p[i].ss=i;
	}
	sort(p+1,p+n+1);
	
	for(int i=1;i<=n;i++)if(p[i].ff<i)
	{
		puts("0");
		return 0;
	}
	
	for(int i=1;i<=n;i++)inv[i]=qpow(i,mod-2);
	pre[0]=suf[n+1]=1;
	for(int i=1;i<=n;i++)pre[i]=(LL)pre[i-1]*(p[i].ff-i+1)%mod;
	for(int i=n;i>=1;i--)suf[i]=(LL)suf[i+1]*(p[i].ff-i+1)%mod;
	
	int cur=1,ans=0,cnt=0;
	for(int i=1;i<=n;i++)
	{
		int val1=query(n),val2=query(p[i].ss);val1-=val2;if(val1<0)val1+=mod;
		ans=(ans+(LL)(val2-val1+mod)*suf[i+1]%mod*cur)%mod;
		if(p[i].ff==i)
		{
			roll_back();
			cur=1;
		}
		else
		{
			int v=(LL)pre[i]*qpow(cur,mod-2)%mod;
			add(p[i].ss,v);
			vs.pb(mp(p[i].ss,v));
			cur=(LL)cur*(p[i].ff-i)%mod;
		}
	}
	if(ans&1)ans+=mod;ans>>=1;
	
	memset(bit,0,sizeof(bit));
	for(int i=1;i<=n;i++)
	{
		cnt+=i-1-query(p[i].ss);if(cnt>=mod)cnt-=mod;
		add(p[i].ss,1);
	}
	ans=(ans+(LL)pre[n]*cnt)%mod;
	printendl(ans);
	return 0;
}
```