#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#include<assert.h>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
#define SZ(x) ((int)x.size())
using namespace std;
inline LL read()
{
	LL f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int stack[20];
template<typename T>inline void write(T x)
{
	if(x<0){putchar('-');x=-x;}
    if(!x){putchar('0');return;}
    int top=0;
    while(x)stack[++top]=x%10,x/=10;
    while(top)putchar(stack[top--]+'0');
}
template<typename T>inline void pr1(T x){write(x);putchar(' ');}
template<typename T>inline void pr2(T x){write(x);putchar('\n');}
template<typename T>inline void chkmin(T &x,T y){x=x<y?x:y;}
template<typename T>inline void chkmax(T &x,T y){x=x>y?x:y;}
const int MAXN=200005;
const int mod=1e9+7;
const int inv2=(mod+1)>>1;
int pow_mod(int a,int b)
{
	int ret=1;
	for(;b;b>>=1,a=1LL*a*a%mod)if(b&1)ret=1LL*ret*a%mod;
	return ret;
}
int n,a[MAXN];
void ad(int &x,int y){x+=y;if(x>=mod)x-=mod;}
struct bittree
{
	int bit[MAXN];
	int lowbit(int x){return x&-x;}
	void modify(int x,int c){for(;x<=n;x+=lowbit(x))ad(bit[x],c);}
	int qry(int x){int ret=0;for(;x>=1;x-=lowbit(x))ad(ret,bit[x]);return ret;}
}bi,bi1,bi2;
int id[MAXN],d[MAXN],nxt[MAXN],pre[MAXN],rnk[MAXN];
bool cmp(int n1,int n2){return a[n1]<a[n2];}
int main()
{
//	freopen("e.in","r",stdin);
//	freopen("e.out","w",stdout);
	n=read();for(int i=1;i<=n;i++)a[i]=read(),id[i]=i;
	sort(id+1,id+1+n,cmp);int sum=1;
	for(int i=1;i<=n;i++)rnk[id[i]]=i;
	for(int i=1;i<=n;i++)sum=1LL*sum*(a[id[i]]-i+1)%mod;if(!sum)return pr2(0),0;
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		int u=id[i];
		d[i]=1LL*pow_mod(a[u]-i+1,mod-2)*(a[u]-i)%mod;
		d[i]=d[i-1]?1LL*d[i-1]*d[i]%mod:d[i];
	}nxt[n+1]=n+1;
	for(int i=1;i<=n;i++)pre[i]=(!d[i-1]?i-1:pre[i-1]);
	for(int i=n;i>=1;i--)nxt[i]=(!d[i+1]?i+1:nxt[i+1]);
	for(int i=n;i>=1;i--)
	{
		int u=rnk[i];
		int nx=(bi.qry(nxt[u])-bi.qry(u-1)+mod)%mod;
		nx=1LL*nx*pow_mod(d[u],mod-2)%mod*(a[i]-u)%mod;
		ad(ans,1LL*nx*inv2%mod*sum%mod);
		bi.modify(u,1LL*pow_mod(a[i]-u+1,mod-2)*d[u-1]%mod);
		
		nx=(bi2.qry(u)-bi2.qry(pre[u]-1)+mod)%mod;int tot=bi1.qry(u);
		nx=1LL*nx*d[u-1]%mod*pow_mod(a[i]-u+1,mod-2)%mod;
		nx=1LL*nx*inv2%mod*sum%mod;
		nx=(1LL*sum*tot%mod-nx+mod)%mod;
		ad(ans,nx);
		bi1.modify(u,1);
		int val=(a[i]-u);
		if(d[u])bi2.modify(u,1LL*val*pow_mod(d[u],mod-2)%mod);
		else bi2.modify(u,val);
	}pr2(ans);
	return 0;
}

### Prompt

Please formulate 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
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#include<assert.h>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
#define SZ(x) ((int)x.size())
using namespace std;
inline LL read()
{
	LL f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int stack[20];
template<typename T>inline void write(T x)
{
	if(x<0){putchar('-');x=-x;}
    if(!x){putchar('0');return;}
    int top=0;
    while(x)stack[++top]=x%10,x/=10;
    while(top)putchar(stack[top--]+'0');
}
template<typename T>inline void pr1(T x){write(x);putchar(' ');}
template<typename T>inline void pr2(T x){write(x);putchar('\n');}
template<typename T>inline void chkmin(T &x,T y){x=x<y?x:y;}
template<typename T>inline void chkmax(T &x,T y){x=x>y?x:y;}
const int MAXN=200005;
const int mod=1e9+7;
const int inv2=(mod+1)>>1;
int pow_mod(int a,int b)
{
	int ret=1;
	for(;b;b>>=1,a=1LL*a*a%mod)if(b&1)ret=1LL*ret*a%mod;
	return ret;
}
int n,a[MAXN];
void ad(int &x,int y){x+=y;if(x>=mod)x-=mod;}
struct bittree
{
	int bit[MAXN];
	int lowbit(int x){return x&-x;}
	void modify(int x,int c){for(;x<=n;x+=lowbit(x))ad(bit[x],c);}
	int qry(int x){int ret=0;for(;x>=1;x-=lowbit(x))ad(ret,bit[x]);return ret;}
}bi,bi1,bi2;
int id[MAXN],d[MAXN],nxt[MAXN],pre[MAXN],rnk[MAXN];
bool cmp(int n1,int n2){return a[n1]<a[n2];}
int main()
{
//	freopen("e.in","r",stdin);
//	freopen("e.out","w",stdout);
	n=read();for(int i=1;i<=n;i++)a[i]=read(),id[i]=i;
	sort(id+1,id+1+n,cmp);int sum=1;
	for(int i=1;i<=n;i++)rnk[id[i]]=i;
	for(int i=1;i<=n;i++)sum=1LL*sum*(a[id[i]]-i+1)%mod;if(!sum)return pr2(0),0;
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		int u=id[i];
		d[i]=1LL*pow_mod(a[u]-i+1,mod-2)*(a[u]-i)%mod;
		d[i]=d[i-1]?1LL*d[i-1]*d[i]%mod:d[i];
	}nxt[n+1]=n+1;
	for(int i=1;i<=n;i++)pre[i]=(!d[i-1]?i-1:pre[i-1]);
	for(int i=n;i>=1;i--)nxt[i]=(!d[i+1]?i+1:nxt[i+1]);
	for(int i=n;i>=1;i--)
	{
		int u=rnk[i];
		int nx=(bi.qry(nxt[u])-bi.qry(u-1)+mod)%mod;
		nx=1LL*nx*pow_mod(d[u],mod-2)%mod*(a[i]-u)%mod;
		ad(ans,1LL*nx*inv2%mod*sum%mod);
		bi.modify(u,1LL*pow_mod(a[i]-u+1,mod-2)*d[u-1]%mod);
		
		nx=(bi2.qry(u)-bi2.qry(pre[u]-1)+mod)%mod;int tot=bi1.qry(u);
		nx=1LL*nx*d[u-1]%mod*pow_mod(a[i]-u+1,mod-2)%mod;
		nx=1LL*nx*inv2%mod*sum%mod;
		nx=(1LL*sum*tot%mod-nx+mod)%mod;
		ad(ans,nx);
		bi1.modify(u,1);
		int val=(a[i]-u);
		if(d[u])bi2.modify(u,1LL*val*pow_mod(d[u],mod-2)%mod);
		else bi2.modify(u,val);
	}pr2(ans);
	return 0;
}

```