[NOI Online #2 提高组] 子序列问题

题目背景

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

4
2 1 3 2

输出样例 #1

43

输入样例 #2

3
1 1 1

输出样例 #2

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]$。