You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

序列

题目背景

2s 512M

题目描述

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

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

4
2 1 3 2

样例输出 #1

43

样例 #2

样例输入 #2

3
1 1 1

样例输出 #2

6

提示

对于 $20\%$ 的数据，满足 $1 \leq n \leq 10$；

对于 $40\%$ 的数据，满足 $1 \leq n \leq 1000$；

对于 $60\%$ 的数据，满足 $1\leq n \leq 10^5$；

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