3399. [NOI Online 2020 2nd]子序列问题(民间数据)

【题目描述】

给定一个长度为n的正整数序列 $A_1,A_2, \ldots ,A_n$。定义一个函数$ f(l,r)$ 表示：序列中下标在 $[l,r]$ 范围内的子区间中，不同的整数个数。换句话说，$f(l,r)$ 就是集合 ${A_l,A_{l+1},\ldots,A_r}$ 的大小，这里的集合是不可重集，即集合中的元素互不相等。

现在，请你求出$ \sum_{l=1}^{n} \sum_{r=1}^{n}f(l,r)^2$.由于答案可能很大，请输出答案对$10^9+7$取模的结果。

【输入格式】

第一行一个正整数 $n$,表示序列的长度。

第二行 $n$ 个正整数，相邻两个整数用空格隔开，表示序列$A_1,A_2, \ldots ,A_n$。

【输出格式】

仅一行一个非负整数，表示答案对 $10^9+7$ 取模的结果。

【样例输入1】

4
2 1 3 2

【样例输出1】

43

【样例输入2】

3
1 1 1

【样例输出2】

6

【提示】

对于$10\%$的数据，满足 $1≤n≤10$;

对于$30\%$的数据，满足 $1≤n≤100$;

对于$50\%$的数据，满足 $1≤n≤10^3$;

对于$70\%$的数据，满足 $1≤n≤10^5$;

对于$100\%$的数据，满足 $1≤n≤10^6$,集合中每个数的范围是$[1,10^9]$。

【来源】

NOI Online2020 提高组 第二轮 Task 2