问题2864--子序列问题(NOI Online2 lfw数据)

2864: 子序列问题(NOI Online2 lfw数据)

时间限制: 3 Sec  内存限制: 512 MB
提交: 18  解决: 15
[提交] [状态] [讨论版] [命题人:]

题目描述

给定一个长度为n的正整数序列A1,A2,...,An。定义一个函数f(l,r)表示:序列中下标在[l, r]范围内的子区间中,不同的整数个数。换句话说,f(l,r)就是集合{Al, Al+1, …, Ar}的大小,这里的集合是不可重集,即集合中的元素互不相等。
现在,请你求出sum(f(l,r)^2) (1<=l<=r<=n)。由于答案可能很大,请输出答案对10^9+7取模的结果。

输入

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

输出

第二行n个正整数,相邻两个正整数用空格隔开,表示序列A1,A2,…,An

样例输入 Copy

4
2 1 3 2

样例输出 Copy

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<=Ai<=10^9

来源/分类