题目背景

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$ 取模的结果。

4
2 1 3 2

43

3
1 1 1

6

提示

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

对于 $30\%$ 的数据，满足 $1 \leq n \leq 100$；

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

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

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