使用线段树维护

假设$g[i]$=${\sum_{i=1}^n}f(i,k)^2$
可以用$g[i-1]$推出来$g[i]$
$g[k]$= $g[k-1]$+${2f(t+1,k)}$+$2f(t+2,k)$+$…$+$2f(k-1,k-1)$+$k-t$
此处t是上一个数组中元素为$a[k]$的位置
维护一个$f(i,k)$的区间和就行了,例如$f(1,k)$+$…$+$f(k,k)$

#include <iostream>
#include <unordered_map>
using namespace std;
typedef long long ll;
inline int read()
{
  register int X=0;
  register char ch=0,w=0;
  while(ch<48||ch>57)ch=getchar(),w|=(ch=='-');
  while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
  return w?-X:X;
}
const ll mod=1e9+7;
const ll N=1e6+10;
unordered_map<ll,ll> mp;
ll tr[N<<2];
ll add[N<<2];
int arr[N];
inline void pushup(register ll u){
    tr[u]=tr[u<<1]+tr[u<<1|1];
}
inline void pushdown(register ll l,register ll r,register ll u){
    if(add[u]){
        register ll mid=l+r>>1;
        (tr[u<<1]+=(mid-l+1)*add[u])%=mod;
        (tr[u<<1|1]+=(r-mid)*add[u])%=mod;
        (add[u<<1]+=add[u])%=mod;
        (add[u<<1|1]+=add[u])%=mod;
        add[u]=0;
    }
}
void build(register ll l,register ll r,register ll u){
    if(l==r){
        tr[u]=add[u]=0;
        return ;
    }
    register ll mid=l+r>>1;
    build(l,mid,u<<1),build(mid+1,r,u<<1|1);
    pushup(u);
}
inline void update(register ll l,register ll r,register ll a,register ll b,register ll d,register ll u){
    if(l<=a&&b<=r){
        tr[u]=(tr[u]+d*(b-a+1))%mod;
        add[u]=(add[u]+d)%mod;
        return ;
    }
    pushdown(a,b,u);
    register ll mid=a+b>>1;
    if(l<=mid)update(l,r,a,mid,d,u<<1);
    if(r>mid )update(l,r,mid+1,b,d,u<<1|1);
    pushup(u);
}
inline ll query(register ll l,register ll r,register ll a,register ll b,register ll u){
    if(l<=a&&b<=r){
        return tr[u];
    }
    pushdown(a,b,u);
    register ll mid=a+b>>1;
    register ll ans=0;
    if(l<=mid)ans=(ans+query(l,r,a,mid,u<<1))%mod;
    if(r>mid )ans=(ans+query(l,r,mid+1,b,u<<1|1))%mod;
    return ans;
}
int main()
{
    register ll n;
    n=read();
    for(register ll i=1;i<=n;i++)arr[i]=read();
    for(register ll i=1;i<=n;i++)mp[arr[i]]=0;
    build(1,n,1);
    register ll ans=0;
    register ll p=0;
    for(register ll i=1;i<=n;i++){
        register ll l=mp[arr[i]]+1,r=i;
        p=(p+2*query(l,r,1,n,1)+r-l+1)%mod;
        ans=(ans+p)%mod;
        update(l,r,1,n,1,1);
        mp[arr[i]]=i;
    }
    cout<<ans<<endl;
}