last

#pragma comment(linker, "/STACK:16777216")

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<ctype.h>
#include<assert.h>
#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<string>
#include<utility>
#include<algorithm>
#include<list>
using namespace std;

#define CLR(a) memset(a,0,sizeof(a))
#define SET(a) memset(a,-1,sizeof(a))
#define pb push_back
#define SZ(a) ((long)a.size())
#define ALL(a) a.begin(),a.end()
#define FOREACH(i, c) for( __typeof( (c).begin() ) i = (c).begin(); i != (c).end(); ++i )
#define AREA2(x1,y1,x2,y2,x3,y3) ( x1*(y2-y3) + x2*(y3-y1) + x3*(y1-y2) )
#define SQR(x) ((x)*(x))
#define STR string
#define IT iterator
#define ff first
#define ss second
#define MP make_pair
#define EPS 1e-9
#define INF 1000000007

#define chk(a,k) ((bool)(a&(1<<(k))))
#define set0(a,k) (a&(~(1<<(k))))
#define set1(a,k) (a|(1<<(k)))

typedef long long Long;
typedef vector<long> Vl;
typedef vector<double> VD;
typedef vector<Long> VL;
typedef pair<long,long> Pll;
typedef pair<Long,Long> PLL;

inline long FastMax(long x, long y) { return (((y-x)>>(32-1))&(x^y))^y; }
inline long FastMin(long x, long y) { return (((y-x)>>(32-1))&(x^y))^x; }

long IR[] = { 0,-1,0,1,-1,-1,1,1 };
long IC[] = { 1,0,-1,0,1,-1,-1,1 };

#define MAX 100007
#define MOD 1000000007

Long nCr[MAX+7][14];
Long N;
Long A[MAX+7];
vector<VL> col;
vector<VL> first_grp,second_grp;
vector<Long> arc_list[MAX+7];

void update_BIT( VL &A, Long i, Long v ){

    if( !v ) return;
    while( i and i<A.size() ){
        A[i] += v;
        i += i&-i;
    }
}

Long find_BIT( VL &A, Long i ){

    if( i<0 ) return 0;
    i = min( i,(Long)A.size()-1 );
    Long s = 0;
    while( i ){
        s += A[i];
        s %= MOD;
        i -= i&-i;
    }
    return s;
}

Long range_BIT( VL &A, Long i, Long j ){

    if( i>j ) return 0;
    return ( find_BIT( A, j ) - find_BIT( A,i-1 ) )%MOD;
}



int main( void ){

    Long i,j,Icase,k = 0;

    freopen("text1.txt","r",stdin );

    nCr[0][0] = 1;
    for( i=1;i<=MAX;i++ ){
        nCr[i][0] = 1;
        if( i<=10 ) nCr[i][i] = 1;
        for( j=1;j<=min( 10LL,i-1 );j++ ){
            nCr[i][j] = ( nCr[i-1][j] + nCr[i-1][j-1] )%MOD;
        }
    }

    cin>>N;
    col.resize( MAX+7 );
    for( i=1;i<=N;i++ ){
        cin>>A[i];
        col[A[i]].pb( i );
    }
    Long Lim = (Long)sqrt(N)+1;
    for( i=0;i<=MAX;i++ ){
        if( !col[i].size() ) continue;
        if( 0 and col[i].size() <= Lim ) first_grp.pb( col[i] );
        else second_grp.pb( col[i] );
    }
    /****************************/
    /*calculation for first grp*/
    /***************************/
    Long ans1 = 0;
    for( i=0;i<first_grp.size();i++ ){
        ans1 -= nCr[first_grp[i].size()][4];
        ans1 %= MOD;
        for( j=0;j<first_grp[i].size();j++ ){
            for( k=j+1;k<first_grp[i].size();k++ ){
                arc_list[first_grp[i][k]].pb( first_grp[i][j]);
            }
        }
    }
    vector<Long> st_BIT( N+7 ),ed_BIT( N+7 );
    Long t = 0;
    for( i=1;i<=MAX;i++ ){
        for( j=0;j<arc_list[i].size();j++ ){
            Long u = arc_list[i][j],v = i;
            ans1 += t;
            ans1 %= MOD;
            ans1 -= range_BIT( ed_BIT, 1, u );
            ans1 %= MOD;
            ans1 -= range_BIT( st_BIT, u, v );
            ans1 %= MOD;
        }
        for( j=0;j<arc_list[i].size();j++ ){
            update_BIT( st_BIT, arc_list[i][j], 1 );
        }
        update_BIT( ed_BIT, i, arc_list[i].size() );
        t += arc_list[i].size();
    }

    /****************************/
    /*calculation for second grp*/
    /***************************/
    Long ans2 = 0;
    for( i=0;i<second_grp.size();i++ ){
        for( j=i+1;j<second_grp.size();j++ ){
            ans2 += nCr[second_grp[i].size()][2] * nCr[second_grp[j].size()][2];
            ans2 %= MOD;
        }
    }
    for( i=0;i<second_grp.size();i++ ){
        if( second_grp[i].size() <= 1 ) continue;
        for( j=0;j<second_grp.size();j++ ){
            if( i==j or second_grp[j].size() <= 1 ) continue;
            for( k=1;k<second_grp[i].size();k++ ){
                Long u = second_grp[i][k-1],v = second_grp[i][k];
                Long uI = lower_bound( ALL( second_grp[j] ), u ) - second_grp[j].begin();
                Long vI = upper_bound( ALL( second_grp[j] ), v ) - second_grp[j].begin();
                vI--;
                if( uI>= second_grp[j].size()) continue;
                else if( vI<0 ) continue;
                else if( uI>vI ) continue;
                ans2 -= nCr[second_grp[i].size()][2] * nCr[vI-uI+1][2];
                ans2 %= MOD;
            }
            for( k=1;k<second_grp[i].size();k++ ){
                Long v = second_grp[i][k];
                Long vI = lower_bound( ALL( second_grp[j] ), v ) - second_grp[j].begin();
                ans2 -= nCr[k+1][2] * nCr[second_grp[j].size()-vI][2];
                ans2 %= MOD;
            }
        }
    }

    cout<<ans2<<endl;


    return 0;
}