千万不要像我这个sb，独立推出正解以为可以AC，结果先是一个变量没开 \(long long\)，又是被卡常线段树，最后混了和暴力一样的 \(50\) 分（还好是赛后补题
区间两大套路：前缀和，固定一端点
不妨先考虑 \(\sum_{r=1}^n(f(1,r)^2)\) 的值，设序列 \(b_i=f(1,i)\)，然后枚举 \(1->n\)，对于 \(a_i\)，如果它不是第一次出现，那么显然 \(f(1,i)~f(1,n)\) 都要减去一，最后 \(\sum_{i=1}^n(b_i^2)\) 就是答案。
区间减，区间求平方和，一看就很可做。先不考虑做法来继续看：
假设已经求过了 \(\sum={r=l}^n(f(l,r)^2)\)，我们现在把 \(l\) 换成 \(l+1\)（所以其实我们每次计算的时候是确定左端点 \(l\) 再计算的）。显然 \(f(1,l+1）~f(1,n)\) 都再减去一。但注意到去掉了 \(a_l\) 意味着 \(l+1~n\) 中第一个值为 \(a_l\) 的元素会被统计进去（以前因为 \(a_l\) 存在的原因这个元素会被忽略）。设 \(next_i=\min_{i<j<=n}\{j\mid a_j=a_i\}\)，特殊地，当不存在这样的 \(j\) 的时候 \(next_i\) 为 \(n+1\). 显然 \(next\) 可以对 \(a\) 离散化后 \(O(n)\) 求出。那么我们每次 \(l\) 左移的时候要把 \(f(1,next_l)~f(1,n)\) 再加上一。最后每次计算 \(f(1,l)~f(1,n)\) 的平方和就是答案。
需要维护的多了个加法，区间加减，区间平方和。做过火柴排队的我看到平方就想到先拆式子：
\[(a_1+k)^2+(a_2+k)^2+...+(a_n+k)^2 \] \[=a_1^2+a_2^2+...+a_n^2+n\times k^2+2k(a_1+a_2+...+a_n) \]好了线段树可做，只需要同时维护区间和，区间平方和就行了。
但是这题卡常（我卡过去以后最慢点Luogu测下来1.85秒），建议写树状数组，维护方法和线段树是一样的（但我懒得写了）
为啥除夕晚上不看春晚在写题？即没有npy， 要是不抓紧时间 CSP-S 2021 怎么混上 300分，CF怎么混上Candidate Master，AT怎么打到橙名？
卡常时间到
#include<bits/stdc++.h>
#define rep(i,a,b) for(ll i=(a);i<=(b);i++)
#define per(i,a,b) for(ll i=(a);i>=(b);i--)
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
using namespace std;
typedef long long ll;
typedef double db;
const int MAXN=1e6+10,moder=1e9+7;
int n,a[MAXN],b[MAXN],tot;
int next[MAXN],pre[MAXN],vis[MAXN];
ll ans;
struct SegmentTree{
ll sum[MAXN<<2],sum2[MAXN<<2],tag[MAXN<<2],lp[MAXN<<2],rp[MAXN<<2];
void build(int x,int l,int r){
lp[x]=l,rp[x]=r;
int mid=(l+r)>>1;
if(l==r){sum[x]=l,sum2[x]=1LL*l*l;return;}
build(lc(x),l,mid);build(rc(x),mid+1,r);
push_up(x);
}
inline void push_up(int x){
sum[x]=sum[lc(x)]+sum[rc(x)];
sum2[x]=sum2[lc(x)]+sum2[rc(x)];
}
inline void push_down(int x){
if(!tag[x])return;
int l=lp[x],r=rp[x];
int mid=(l+r)>>1;
sum2[lc(x)]=sum2[lc(x)]+2*tag[x]*sum[lc(x)]+(mid-l+1)*tag[x]*tag[x];
sum2[rc(x)]=sum2[rc(x)]+2*tag[x]*sum[rc(x)]+(r-mid)*tag[x]*tag[x];
sum[lc(x)]=sum[lc(x)]+(mid-l+1)*tag[x];
sum[rc(x)]=sum[rc(x)]+(r-mid)*tag[x];
tag[lc(x)]+=tag[x],tag[rc(x)]+=tag[x],tag[x]=0;
}
void add(int x,int ql,int qr,ll k){
int l=lp[x],r=rp[x];
if(ql<=l&&qr>=r){
sum2[x]=sum2[x]+2*k*sum[x]+(r-l+1)*k*k;
sum[x]=sum[x]+(r-l+1)*k;
tag[x]+=k;
return;
}
push_down(x);
int mid=(l+r)>>1;
if(ql<=mid)add(lc(x),ql,qr,k);
if(qr>mid)add(rc(x),ql,qr,k);
push_up(x);
}
ll query(int x,int ql,int qr){
int l=lp[x],r=rp[x];
if(ql<=l&&qr>=r)return sum2[x];
push_down(x);
ll mid=(l+r)>>1,ret=0;
if(ql<=mid)ret+=query(lc(x),ql,qr);
if(qr>mid)ret+=query(rc(x),ql,qr);
push_up(x);
return ret;
}
}tree;
inline int read(){
int num=0;char ch;
while((ch=getchar()) && !isdigit(ch));
num=ch-'0';
while((ch=getchar()) && isdigit(ch))num=num*10+ch-'0';
return num;
}
int main(){
n=read();
rep(i,1,n)a[i]=read(),b[i]=a[i];
sort(b+1,b+1+n);
tot=unique(b+1,b+1+n)-b;
tree.build(1,1,n);
per(i,n,1){
a[i]=lower_bound(b+1,b+tot,a[i])-b;
if(vis[a[i]])next[i]=vis[a[i]],pre[next[i]]=1;
else next[i]=n+1;
vis[a[i]]=i;
}
rep(i,1,n){
if(pre[i])tree.add(1,i,n,-1);
}
ans=tree.query(1,1,n);
rep(i,2,n){
tree.add(1,i,n,-1);
if(next[i-1]!=n+1)tree.add(1,next[i-1],n,1);
ans=(ans+tree.query(1,i,n))%moder;
}
printf("%lld\n",ans%moder);
return 0;
}