子序列问题

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

给定一个长度为 $n$ 的正整数序列 $A_1,A_2,\ldots,A_n$。

定义 $f(l,r)$ 为子数组 $A_l,A_{l+1},\ldots,A_r$ 中不同整数的个数。求

对 $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

数据范围

对于所有数据，保证 $1\le n\le10^6$，$1\le A_i\le10^9$。