#include <bits/stdc++.h>
using namespace std;

#define LL long long
#define LD long double
#define SC(t,x) static_cast<t>(x)
#define AR(t) vector < t >
#define PII pair < int, int >
#define PLL pair < LL, LL >
#define PIL pair < int, LL >
#define PLI pair < LL, int >
#define MP make_pair
#define PB push_back
#define PF push_front
#define POB pop_back
#define POF pop_front
#define PRF first
#define PRS second
#define INIT(ar,val) memset ( ar, val, sizeof ( ar ) )
#define lp(loop,start,end) for ( int loop = start; loop < end; ++loop )
#define lpd(loop,start,end) for ( int loop = start; loop > end; --loop )
#define lpi(loop,start,end) for ( int loop = start; loop <= end; ++loop )
#define lpdi(loop,start,end) for ( int loop = start; loop >= end; --loop )
#define qmax(a,b) (((a)>(b))?(a):(b))
#define qmin(a,b) (((a)<(b))?(a):(b))
#define qabs(a) (((a)>=0)?(a):(-(a)))

const int INF = 0x3fffffff;
const int SINF = 0x7fffffff;
const long long LINF = 0x3fffffffffffffff;
const long long SLINF = 0x7fffffffffffffff;
const int MAXN = 200007;
const int MOD = SC ( int, 1e9 + 7 );
const int R2 = 500000004;



int add ( int x, int y )
{
	x += y;
	if ( x >= MOD ) x -= MOD;
	return x;
}

void addv ( int &x, int y )
{
	x += y;
	if ( x >= MOD ) x -= MOD;
}

int dec ( int x, int y )
{
	x -= y;
	if ( x < 0 ) x += MOD;
	return x;
}

void decv ( int &x, int y )
{
	x -= y;
	if ( x < 0 ) x += MOD;
}

int qpow ( int a, int b )
{
	LL base = a, ans = 1;
	while ( b ){
		if ( b & 1 ) ( ans *= base ) %= MOD;
		( base *= base ) %= MOD;
		b >>= 1;
	}
	return SC ( int, ans );
}



class ftT
{
public:
	void clear ()
	{
		INIT ( data, 0 );
	}
	
	void upd ( int p, int x )
	{
		for ( ; p < MAXN; p += p&-p ) addv ( data[p], x );
	}
	
	int sum ( int p )
	{
		int ans = 0;
		for ( ; p; p ^= p&-p ) addv ( ans, data[p] );
		return ans;
	}
	
	int query ( int l, int r )
	{
		return ( l <= r ) ? dec ( sum ( r ), sum ( l - 1 ) ) : 0;
	}
	
private:
	int data[MAXN];
}ft;

int n;
int a[MAXN];
int c[MAXN];
int v[MAXN], rv[MAXN];
int pl[MAXN];

void init ();
void input ();
void work ();



int main()
{
	init();
	input();
	work();
}



void init ()
{
	// Init Everything Here
	
	ios::sync_with_stdio ( false );
}

void input ()
{
	// input method
	
	scanf ( "%d", &n );
	lpi ( i, 1, n ) scanf ( "%d", &a[i] );
}

void work ()
{
	// main work
	
	lpi ( i, 1, n ) ++c[a[i]];
	lpd ( i, n, 0 ) c[i] += c[i+1];
	lpi ( i, 1, n ) c[i] -= ( n - i );
	
//	lpi ( i, 1, n ) cerr << c[i] << " "; cerr << endl;
	
	lpi ( i, 1, n ){
		if ( c[i] <= 0 ){
			printf ( "0\n" );
			return;
		}else if ( c[i] == 1 ) pl[i] = i;
		else pl[i] = pl[i-1];
	}
	
//	lpi ( i, 1, n ) cerr << pl[i] << " "; cerr << endl;
	
	int cc = 1;
	lpi ( i, 1, n ) cc = SC ( LL, cc ) * c[i] % MOD;
	
//	cerr << cc << endl;
	
	v[0] = 1;
	lpi ( i, 1, n ) v[i] = ( c[i] ^ 1 ) ? ( SC ( int, SC ( LL, c[i] - 1 ) * qpow ( c[i], MOD-2 ) % MOD * v[i-1] % MOD ) ) : 1, rv[i] = qpow ( v[i], MOD-2 );
	
//	lpi ( i, 1, n ) cerr << v[i] << " "; cerr << endl;
//	lpi ( i, 1, n ) cerr << rv[i] << " "; cerr << endl;
	
	int orig_inv = 0;
	lpd ( i, n, 0 ){
		addv ( orig_inv, ft.sum ( a[i] - 1 ) );
		ft.upd ( a[i], 1 );
	}
//	cerr << orig_inv << endl;
	
	int ans = 0;
	ft.clear ();
	int tv = 0;
	lpi ( i, 1, n ){
		addv ( tv, SC ( LL, cc ) * v[a[i]] % MOD * ft.query ( pl[a[i]]+1, a[i] ) % MOD );
//		cerr << tv << endl;
		ft.upd ( a[i], rv[a[i]] );
	}
	ans = SC ( LL, tv ) * R2 % MOD;
	
	ft.clear ();
	tv = 0;
	lpd ( i, n, 0 ){
		addv ( tv, SC ( LL, cc ) * v[a[i]] % MOD * ft.query ( pl[a[i]]+1, a[i]-1 ) % MOD );
		ft.upd ( a[i], rv[a[i]] );
	}
	addv ( ans, dec ( SC ( LL, cc ) * orig_inv % MOD, SC ( LL, tv ) * R2 % MOD ) );
	
	cout << ans << endl;
}
### Prompt

Construct a Cpp code solution to the problem outlined:

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 <bits/stdc++.h>
using namespace std;

#define LL long long
#define LD long double
#define SC(t,x) static_cast<t>(x)
#define AR(t) vector < t >
#define PII pair < int, int >
#define PLL pair < LL, LL >
#define PIL pair < int, LL >
#define PLI pair < LL, int >
#define MP make_pair
#define PB push_back
#define PF push_front
#define POB pop_back
#define POF pop_front
#define PRF first
#define PRS second
#define INIT(ar,val) memset ( ar, val, sizeof ( ar ) )
#define lp(loop,start,end) for ( int loop = start; loop < end; ++loop )
#define lpd(loop,start,end) for ( int loop = start; loop > end; --loop )
#define lpi(loop,start,end) for ( int loop = start; loop <= end; ++loop )
#define lpdi(loop,start,end) for ( int loop = start; loop >= end; --loop )
#define qmax(a,b) (((a)>(b))?(a):(b))
#define qmin(a,b) (((a)<(b))?(a):(b))
#define qabs(a) (((a)>=0)?(a):(-(a)))

const int INF = 0x3fffffff;
const int SINF = 0x7fffffff;
const long long LINF = 0x3fffffffffffffff;
const long long SLINF = 0x7fffffffffffffff;
const int MAXN = 200007;
const int MOD = SC ( int, 1e9 + 7 );
const int R2 = 500000004;



int add ( int x, int y )
{
	x += y;
	if ( x >= MOD ) x -= MOD;
	return x;
}

void addv ( int &x, int y )
{
	x += y;
	if ( x >= MOD ) x -= MOD;
}

int dec ( int x, int y )
{
	x -= y;
	if ( x < 0 ) x += MOD;
	return x;
}

void decv ( int &x, int y )
{
	x -= y;
	if ( x < 0 ) x += MOD;
}

int qpow ( int a, int b )
{
	LL base = a, ans = 1;
	while ( b ){
		if ( b & 1 ) ( ans *= base ) %= MOD;
		( base *= base ) %= MOD;
		b >>= 1;
	}
	return SC ( int, ans );
}



class ftT
{
public:
	void clear ()
	{
		INIT ( data, 0 );
	}
	
	void upd ( int p, int x )
	{
		for ( ; p < MAXN; p += p&-p ) addv ( data[p], x );
	}
	
	int sum ( int p )
	{
		int ans = 0;
		for ( ; p; p ^= p&-p ) addv ( ans, data[p] );
		return ans;
	}
	
	int query ( int l, int r )
	{
		return ( l <= r ) ? dec ( sum ( r ), sum ( l - 1 ) ) : 0;
	}
	
private:
	int data[MAXN];
}ft;

int n;
int a[MAXN];
int c[MAXN];
int v[MAXN], rv[MAXN];
int pl[MAXN];

void init ();
void input ();
void work ();



int main()
{
	init();
	input();
	work();
}



void init ()
{
	// Init Everything Here
	
	ios::sync_with_stdio ( false );
}

void input ()
{
	// input method
	
	scanf ( "%d", &n );
	lpi ( i, 1, n ) scanf ( "%d", &a[i] );
}

void work ()
{
	// main work
	
	lpi ( i, 1, n ) ++c[a[i]];
	lpd ( i, n, 0 ) c[i] += c[i+1];
	lpi ( i, 1, n ) c[i] -= ( n - i );
	
//	lpi ( i, 1, n ) cerr << c[i] << " "; cerr << endl;
	
	lpi ( i, 1, n ){
		if ( c[i] <= 0 ){
			printf ( "0\n" );
			return;
		}else if ( c[i] == 1 ) pl[i] = i;
		else pl[i] = pl[i-1];
	}
	
//	lpi ( i, 1, n ) cerr << pl[i] << " "; cerr << endl;
	
	int cc = 1;
	lpi ( i, 1, n ) cc = SC ( LL, cc ) * c[i] % MOD;
	
//	cerr << cc << endl;
	
	v[0] = 1;
	lpi ( i, 1, n ) v[i] = ( c[i] ^ 1 ) ? ( SC ( int, SC ( LL, c[i] - 1 ) * qpow ( c[i], MOD-2 ) % MOD * v[i-1] % MOD ) ) : 1, rv[i] = qpow ( v[i], MOD-2 );
	
//	lpi ( i, 1, n ) cerr << v[i] << " "; cerr << endl;
//	lpi ( i, 1, n ) cerr << rv[i] << " "; cerr << endl;
	
	int orig_inv = 0;
	lpd ( i, n, 0 ){
		addv ( orig_inv, ft.sum ( a[i] - 1 ) );
		ft.upd ( a[i], 1 );
	}
//	cerr << orig_inv << endl;
	
	int ans = 0;
	ft.clear ();
	int tv = 0;
	lpi ( i, 1, n ){
		addv ( tv, SC ( LL, cc ) * v[a[i]] % MOD * ft.query ( pl[a[i]]+1, a[i] ) % MOD );
//		cerr << tv << endl;
		ft.upd ( a[i], rv[a[i]] );
	}
	ans = SC ( LL, tv ) * R2 % MOD;
	
	ft.clear ();
	tv = 0;
	lpd ( i, n, 0 ){
		addv ( tv, SC ( LL, cc ) * v[a[i]] % MOD * ft.query ( pl[a[i]]+1, a[i]-1 ) % MOD );
		ft.upd ( a[i], rv[a[i]] );
	}
	addv ( ans, dec ( SC ( LL, cc ) * orig_inv % MOD, SC ( LL, tv ) * R2 % MOD ) );
	
	cout << ans << endl;
}
```