#include<cstdio>
#include<vector>
#include<cstring>
#define N 300001
#define M 5001
#define mod 1000000007
using namespace std;
int a[N];
long long count[N],dj[N];
long long hz[N];
long long f[5][N],beh[N];
long long qz[N],front[N],zero[N],p[N];
int n;
vector<int>place[N];
long long ksmi(long long x,long long y)
{
	long long p=y,ab=x,total=1;
	while (p)
	{
		if (p%2==1) total=total*ab%mod;
		ab=ab*ab%mod;
		p/=2;
	}
	return total;
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	for (int i=1;i<=n;i++) hz[i]--;
	for (int i=1;i<=n;i++) hz[a[i]]++;
	for (int i=n;i>=1;i--) hz[i]+=hz[i+1];
	for (int i=1;i<=n;i++)
		if (hz[i]+1<=0)
		{
			printf("0\n");
			return 0;
		}
	for (int i=1;i<=n;i++) count[a[i]]++;
	for (int i=1;i<=n;i++)
		place[i].resize(count[i]+1);
	memset(count,0,sizeof(count));
	for (int i=1;i<=n;i++)
	{
		count[a[i]]++;
		place[a[i]][count[a[i]]]=i;
	}
	dj[4]=0;dj[3]=-1;dj[2]=-2;dj[1]=-1;dj[0]=0;
	f[0][n+1]=1;
	for (int i=n;i>=1;i--)
	{
		for (int j=4;j>=0;j--)
		{
			if (hz[i]+1+dj[j]<0) continue;
			f[j][i]=(f[j][i]+f[j][i+1]*(hz[i]+1+dj[j])%mod)%mod;
		}
		f[4][i]=(f[4][i]+f[3][i+1])%mod;
		f[3][i]=(f[3][i]+f[2][i+1])%mod;
		if (hz[i]+1+dj[2]>0)
			f[2][i]=(f[2][i]+f[1][i+1]*count[i]%mod*(hz[i]+1+dj[2])%mod)%mod;
		if (hz[i]+1+dj[1]>0)
			f[1][i]=(f[1][i]+f[0][i+1]*count[i]%mod*(hz[i]+1+dj[1])%mod)%mod;
		f[3][i]=(f[3][i]+f[1][i+1]*count[i]%mod)%mod;
		if (hz[i]+1+dj[2]>0)
			f[2][i]=(f[2][i]+f[0][i+1]*(count[i]*(count[i]-1)/2)%mod*(hz[i]+1+dj[2])%mod)%mod;
		f[3][i]=(f[3][i]+f[0][i+1]*(count[i]*(count[i]-1)/2)%mod)%mod;
	}
	long long ans1=f[4][1];
	dj[4]=0;dj[3]=-1;dj[2]=0;dj[1]=-1;
	beh[n+1]=1;
	for (int i=n;i>=1;i--)
		beh[i]=beh[i+1]*(hz[i]+1)%mod;
	front[0]=1;
	for (int i=1;i<=n;i++)
		front[i]=front[i-1]*(hz[i]+1)%mod;
	qz[0]=1;
	for (int i=1;i<=n;i++)
	{
		if (hz[i]!=0)
			qz[i]=qz[i-1]*(hz[i])%mod;
		else	qz[i]=qz[i-1];
	}
	for (int i=1;i<=n;i++)
		if (hz[i]==0) zero[i]=zero[i-1]+1;
		else	zero[i]=zero[i-1];
	for (int i=1;i<=n;i++)
	{
		p[i]=(p[i-1]*hz[i]%mod);
		p[i]=(p[i]+front[i-1])%mod;
	}
	for (int l1=1;l1<=n;l1++)
	{
		long long ans2=0,ans3=0;
		int r=a[l1];
		for (int r1=l1+1;r1<=n;r1++)
		{
			int l=a[r1];
			if (l>=r) continue;
			ans2=(ans2+p[l]*ksmi(front[l],mod-2)%mod)%mod;
			ans3=(ans3+p[l]*p[l]%mod*ksmi(front[l],mod-2)%mod*ksmi(qz[l],mod-2)%mod)%mod;
		}
		ans2=ans2*beh[r+1]%mod*p[r]%mod;
		ans3=ans3*beh[r+1]%mod*qz[r]%mod;
	//	printf("%d %d %lld\n",r1,l1,ans2);
		ans1=(ans1+ans2-ans3+mod)%mod;
	}
	printf("%d\n",ans1);
}