#include<cstdio>
#include<vector>
#include<cstring>
#define N 3000001
#define M 5001
#define mod 1000000007
using namespace std;
int a[N];
long long count[N],dj[N],zhi1[N],zhi2[N],g1[N],g2[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;
}
void update1(int ma,int l,int r,int s,int x)
{
	if (l==r)
	{
		g1[ma]=(g1[ma]+x)%mod;
		return;
	}
	int mid=(l+r)/2;
	if (s<=mid) update1(ma*2,l,mid,s,x);
	else	update1(ma*2+1,mid+1,r,s,x);
	g1[ma]=(g1[ma*2]+g1[ma*2+1])%mod;
}
void update2(int ma,int l,int r,int s,int x)
{
	if (l==r)
	{
		g2[ma]=(g2[ma]+x)%mod;
		return;
	}
	int mid=(l+r)/2;
	if (s<=mid) update2(ma*2,l,mid,s,x);
	else	update2(ma*2+1,mid+1,r,s,x);
	g2[ma]=(g2[ma*2]+g2[ma*2+1])%mod;
}
int find_ans1(int ma,int l,int r,int l1,int r1)
{
	if (l1>r1) return 0;
	if (l==l1&&r==r1) return g1[ma];
	int mid=(l+r)/2;
	if (r1<=mid) return find_ans1(ma*2,l,mid,l1,r1);
	if (mid<l1) return find_ans1(ma*2+1,mid+1,r,l1,r1);
	long long s1=find_ans1(ma*2,l,mid,l1,mid);
	s1=(s1+find_ans1(ma*2+1,mid+1,r,mid+1,r1))%mod;
	return s1;
}
int find_ans2(int ma,int l,int r,int l1,int r1)
{
	if (l1>r1) return 0;
	if (l==l1&&r==r1) return g2[ma];
	int mid=(l+r)/2;
	if (r1<=mid) return find_ans2(ma*2,l,mid,l1,r1);
	if (mid<l1) return find_ans2(ma*2+1,mid+1,r,l1,r1);
	long long s1=find_ans2(ma*2,l,mid,l1,mid);
	s1=(s1+find_ans2(ma*2+1,mid+1,r,mid+1,r1))%mod;
	return s1;
}
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 i=1;i<=n;i++)
	{
		zhi1[i]=p[i]*ksmi(front[i],mod-2)%mod;
		zhi2[i]=p[i]*p[i]%mod*ksmi(front[i],mod-2)%mod*ksmi(qz[i],mod-2)%mod;
	}
	for (int l1=n;l1>=1;l1--)
	{
		if (l1==n-2)
		{
			l1++;l1--;
		}
		int r=a[l1];
		long long ans2=find_ans1(1,1,n,1,r-1),ans3=0;
		int sl=1,sr=r,sans=r;
		while (sl<=sr)
		{
			int mid=(sl+sr)/2;
			if (zero[r]-zero[mid]==0)
			{
				sans=mid;
				sr=mid-1;
			}
			else	sl=mid+1;
		}
		ans3=find_ans2(1,1,n,sans,r-1);
		ans2=ans2*beh[r+1]%mod*p[r]%mod;
		ans3=ans3*beh[r+1]%mod*qz[r]%mod;
		ans1=(ans1+ans2-ans3+mod)%mod;
		//printf("%lld %lld\n",ans2,ans3);
		update1(1,1,n,a[l1],zhi1[a[l1]]);
		update2(1,1,n,a[l1],zhi2[a[l1]]);
	}
	printf("%d\n",ans1);
}

Measured memory_bytes: 132628