简要题意：
给定 (n) 个数 (a_i)，求 (sum_{l=1}^n sum_{r=l}^n (f_{l,r})^2)，(f_{l,r}) 为 (a_l , a_{l+1} cdots a_r) 中 不重复数 的个数。
( ext{NOI ONLINE 2}) 考场 (T2)，比较有思维含量的。
Case 1
对于 (10 \%) 的数据，(n leq 10).
瞎搞分。
Case 2
对于 (30 \%) 的数据，(n leq 100).
考虑枚举左右端点，然后暴力构造区间，用 ( ext{map}) 去重。(O(n^3 log n))，得分 (30pts).
考虑一个优化，可以先将原数组 离散化，然后用桶，(O(n^3))，得分 (30pts).
Case 3
对于 (50 \%) 的数据，(n leq 10^3).
实际上，对于一个固定的左端点 (l)，可以不断往右延伸，对于每一个新的 (r (l leq r leq n)) 都只需用桶新维护一个数，这样可以做到 (O(n^2))，得分 (50pts).
实际上，本人在考场上止步于此，深感遗憾！
Case 4
对于 (70 \%) 的数据，(n leq 10^5).
对于 (100 \%) 的数据，(n leq 10^6)，(a_i leq 10^9).
首先离散化，降值域。我们需要一个 (O(n sqrt{n})) 或 (O(n log n)) 的数据结构。
注意到 平方 不太好维护，所以：
注意到 (x^2 = 2 imes frac{x imes (x-1)}{2} + x)，则令 (g_{l,r} = frac{f_{l,r} imes (f_{l,r}-1)}{2}) ，则计算每个区间 (g_{l,r}+f_{l,r}) 即可。
预处理 (Last_i) 是满足 (a_i = a_j (1 leq j < i)) 中最大的 (j)，不存在则 (Last_i=0)
下面枚举 (r) ，只需计算 (sum_{l=1}^r g_{l,r} + f_{l,r}).
那么考虑 (r ightarrow r+1) 会增加啥？
首先 (sum f_{l,r+1} - f_{l,r} = (r+1) - Last_{r+1})，因为 (i in [Last_{r+1}+1,r+1]) 显然 (f_{i,r+1} - f_{i,r} = 1)，多出了 (a_{r+1})，增加一个。
(g_{l,r}) 怎么搞？
所以用 线段树 维护 (f_{l,r}) 的值，那么显然 (r ightarrow r+1) 需要让 ([Last_{r-1}+1,r+1]) 区间 (+1) 即可。
那 (sum g_{l,r+1} - sum g_{l,r}) 呢？考虑一个公式 (frac{x imes (x+1)}{2} - frac{x imes (x-1)}{2} = x)，所以：
，可以继续用 线段树 维护。
注意：最后询问结果 ( imes 2) 才是最终 (g_{l,r}) 的值，这个细节让我调试了 (0.5h).
时间复杂度：(O(n log n)).
期望得分：(100pts).
实际得分：(75) ~ (100pts).（(10^6) 如果硬卡你常数的话，因为你线段树要都开 ( ext{long long})，不一定能过，要注意常数优化！）
//O3 优化模板
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(5000)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
//代码中所有 i=-~i 等同于 i++ , 用来卡常
//register int 可视为 int , 用来卡常
//inline 和快读都是用来卡常的
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
const int N=1e6+1;
#define L i<<1
#define R i<<1|1
#define DEBUG cout<<__LINE__<<" "<<__FUNCTION__<<endl;
inline int read(){char ch=getchar(); int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}
int n,a[N]; bool q[N];
map<int,int> uni; //离散化工具
int b[N],last[N],gett[N]; //gett[i] 维护 last 构成的桶
ll ans=0;
struct tree{
int l,r; ll tag;
ll sumi;
} t[N<<2];
inline void update(int i) {
t[i].sumi=(t[L].sumi+t[R].sumi)%MOD;
}
inline void pass(int i,ll x) {
t[i].tag=t[i].tag+x;
t[i].sumi=(t[i].sumi+x*(t[i].r-t[i].l+1))%MOD;
}
inline void pushdown(int i) {
pass(L,t[i].tag);
pass(R,t[i].tag);
t[i].tag=0;
}
inline void build_tree(int i,int l,int r) {
t[i].l=l; t[i].r=r; t[i].sumi=0; t[i].tag=0;
if(l==r) return;
int mid=(l+r)>>1;
build_tree(L,l,mid);
build_tree(R,mid+1,r);
// update(i);
}
inline ll query(int i,int l,int r) {
if(l<=t[i].l && t[i].r<=r) return t[i].sumi;
int mid=(t[i].l+t[i].r)>>1; ll ans=0;
pushdown(i);
if(l<=mid) ans=(ans+query(L,l,r))%MOD;
if(r>mid) ans=(ans+query(R,l,r))%MOD;
return ans;
}
inline void change(int i,int l,int r,ll x) {
if(l<=t[i].l && t[i].r<=r) {
t[i].sumi=(t[i].sumi+x*(t[i].r-t[i].l+1))%MOD;
t[i].tag=t[i].tag+x; return ;
} pushdown(i);
int mid=(t[i].l+t[i].r)>>1;
if(l<=mid) change(L,l,r,x);
if(r>mid) change(R,l,r,x);
update(i);
} //线段树模板
int main() {
n=read();
for(register int i=1;i<=n;i=-~i) a[i]=read(),b[i]=a[i];
sort(b+1,b+1+n); int k=1; uni[b[1]]=1;
for(register int i=2;i<=n;i=-~i) {
if(b[i]!=b[i-1]) k++;
uni[b[i]]=k;
}
for(register int i=1;i<=n;i=-~i) a[i]=uni[a[i]];
for(register int i=1;i<=n;i=-~i) {
last[i]=gett[a[i]];
gett[a[i]]=i;
// printf("%d %d
",a[i],last[i]);
} ll s=0; build_tree(1,1,n);
for(register int r=0;r<n;r++) {
ll t=r+1-last[r+1]; //ans=(ans+r-last[r])%MOD;
t=(t+query(1,last[r+1]+1,r+1)*2)%MOD; //t 为增加答案
change(1,last[r+1]+1,r+1,1);
s=(s+t)%MOD; ans=(ans+s)%MOD; //s 为当前贡献，ans 为总答案，注意取模
} printf("%lld
",ans);
return 0;
}