#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define fo(i,a,b) dfo(int,i,a,b)
#define fr(i,n) dfr(int,i,n)
#define fe(i,a,b) dfe(int,i,a,b)
#define fq(i,n) dfq(int,i,n)
#define nfo(i,a,b) dfo(,i,a,b)
#define nfr(i,n) dfr(,i,n)
#define nfe(i,a,b) dfe(,i,a,b)
#define nfq(i,n) dfq(,i,n)
#define dfo(d,i,a,b) for (d i = (a); i < (b); i++)
#define dfr(d,i,n) dfo(d,i,0,n)
#define dfe(d,i,a,b) for (d i = (a); i <= (b); i++)
#define dfq(d,i,n) dfe(d,i,1,n)
#define ffo(i,a,b) dffo(int,i,a,b)
#define ffr(i,n) dffr(int,i,n)
#define ffe(i,a,b) dffe(int,i,a,b)
#define ffq(i,n) dffq(int,i,n)
#define nffo(i,a,b) dffo(,i,a,b)
#define nffr(i,n) dffr(,i,n)
#define nffe(i,a,b) dffe(,i,a,b)
#define nffq(i,n) dffq(,i,n)
#define dffo(d,i,a,b) for (d i = (b)-1; i >= (a); i--)
#define dffr(d,i,n) dffo(d,i,0,n)
#define dffe(d,i,a,b) for (d i = (b); i >= (a); i--)
#define dffq(d,i,n) dffe(d,i,1,n)
#define ll long long
#define alok(n,t) ((t*)malloc((n)*sizeof(t)))
#define pf printf
#define sf scanf
#define pln pf("\n")

#define mod 1000000007

int *x = alok(111111, int);
int *cols = alok(111111, int);
int **vs = alok(111111, int*);
int *ns = alok(111111, int) + 1;
int *ys = alok(111111, int);
int *inds = alok(111111, int);
int *exc = alok(111111, int);
int **tr = alok(20, int*);

int main() {
	ns[-1] = -1;
	ys[0] = 0;
	int n;
	sf("%d", &n);
	fr(i,n) {
		sf("%d", x + i);
		cols[x[i]] = -1;
	}
	int cs = 0;
	fr(i,n) {
		int v = x[i];
		if (!~cols[v]) {
			ns[cs] = 0;
			x[i] = cols[v] = cs++;
		} else {
			x[i] = cols[v];
		}
	}

	fr(i,n) ns[x[i]]++;
	fr(c,cs) {
		vs[c] = alok(ns[c], int);
		exc[c] = 0;
		ns[c] = 0;
	}
	fr(i,n) {
		int c = x[i];
		vs[c][ns[c]++] = i;
	}

	fr(c,cs) fr(i,ns[c]) inds[vs[c][i]] = i;

	int lim = int(sqrt(n/log(n+1))*1.0);
	if (lim < 5) lim = 5;
	ll ct = 0;
	fr(mx,cs) {
		if (ns[mx] <= lim) continue;
		exc[mx] = 1;
		ll wun = ns[mx];
		fr(i,n) {
			ys[i+1] = ys[i];
			if (x[i] == mx) ys[i+1]++;
		}

		fr(c,cs) {
			if (exc[c]) continue;
			ll Bsc = 0;
			ll Csc = 0;
			int *vsc = vs[c];
			int nsc = ns[c];
			fr(i,nsc) {
				ll wl = ys[vsc[i]];
				Bsc += wl;
				Csc += wl*wl;
				if (Bsc >= mod) Bsc -= mod;
				ct -= Bsc*(wun+wl) << 1;
			}
			Csc %= mod;
			ct += Bsc*(Bsc+wun) << 1;
			ct += (Bsc*wun-Csc)*(nsc-1);
			ct %= mod;
		}
	}

	ll ab = 0;
	fr(c,cs) {
		if (exc[c]) continue;
		ll N = ns[c];
		ab += N*(N-1)*(N-2)*(N-3);
	}

	ct -= ab/24;
	ct %= mod;

	ll yt = 0;
	fr(i,n) {
		int c = x[i];
		if (exc[c]) continue;
		ll ctx = ns[c]-inds[i]-1;
		yt += inds[i];
		ct -= ctx*yt;
		ct -= ctx*(ctx-1)>>1;
		ct %= mod;
	}

	int ht = 1;
	for (int sz = n, nsz = sz + 1 >> 1; sz > 1; ht++, sz = nsz, nsz = sz + 1 >> 1);

	for (int h = 0, sz = n << 1, nsz = sz + 1 >> 1; h < ht; h++, sz = nsz, nsz = sz + 1 >> 1) {
		tr[h] = alok(nsz, int);
		fr(i,nsz) tr[h][i] = 0;
	}

	fr(i,n) {
		int c = x[i];
		if (exc[c]) continue;
		int nsc = ns[c];
		int *vsc = vs[c];
		fo(j,inds[i]+1,nsc) {
			int ind = vsc[j];

			for (int I = ind, h = 0; h < ht; I >>= 1, h++) {
				tr[h][I]++;
			}
			
			for (int I = ind, h = 0; I; I >>= 1, h++) {
				if (I & 1) ct += tr[h][--I];
			}
		}
		ct %= mod;
	}

	if (ct < 0) ct += mod;
	pf("%lld\n", ct);
}