Sereja and Subsequences

题意翻译

给你一个序列，把这个序列的每一个不下降子序列拿出来 对于每一个子序列,一个可行序列为: - 由正整数组成,长度和原子串相同 - 不大于原子串 求所有的可行串

题目描述

Sereja has a sequence that consists of $ n $ positive integers, $ a_{1},a_{2},...,a_{n} $ . First Sereja took a piece of squared paper and wrote all distinct non-empty non-decreasing subsequences of sequence $ a $ . Then for each sequence written on the squared paper, Sereja wrote on a piece of lines paper all sequences that do not exceed it. A sequence of positive integers $ x=x_{1},x_{2},...,x_{r} $ doesn't exceed a sequence of positive integers $ y=y_{1},y_{2},...,y_{r} $ , if the following inequation holds: $ x_{1}<=y_{1},x_{2}<=y_{2},...,x_{r}<=y_{r} $ . Now Sereja wonders, how many sequences are written on the lines piece of paper. Help Sereja, find the required quantity modulo $ 1000000007 $ $ (10^{9}+7) $ .

输入输出格式

输入格式

The first line contains integer $ n $ $ (1<=n<=10^{5}) $ . The second line contains $ n $ integers $ a_{1},a_{2},...,a_{n} $ $ (1<=a_{i}<=10^{6}) $ .

输出格式

In the single line print the answer to the problem modulo $ 1000000007 $ $ (10^{9}+7) $ .

输入输出样例

输入样例 #1

1
42

输出样例 #1

42

输入样例 #2

3
1 2 2

输出样例 #2

13

输入样例 #3

5
1 2 3 4 5

输出样例 #3

719