4782: Fence Divercity
内存限制：256 MB
时间限制：2 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：2
通过：1
题目描述
G. Fence Divercity
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Long ago, Vasily built a good fence at his country house. Vasily calls a fence good, if it is a series of n consecutively fastened vertical boards of centimeter width, the height of each in centimeters is a positive integer. The house owner remembers that the height of the i-th board to the left is hi.
Today Vasily decided to change the design of the fence he had built, by cutting his top connected part so that the fence remained good. The cut part should consist of only the upper parts of the boards, while the adjacent parts must be interconnected (share a non-zero length before cutting out of the fence).
You, as Vasily's curious neighbor, will count the number of possible ways to cut exactly one part as is described above. Two ways to cut a part are called distinct, if for the remaining fences there is such i, that the height of the i-th boards vary.
As Vasily's fence can be very high and long, get the remainder after dividing the required number of ways by 1000000007 (109+7).
Today Vasily decided to change the design of the fence he had built, by cutting his top connected part so that the fence remained good. The cut part should consist of only the upper parts of the boards, while the adjacent parts must be interconnected (share a non-zero length before cutting out of the fence).
You, as Vasily's curious neighbor, will count the number of possible ways to cut exactly one part as is described above. Two ways to cut a part are called distinct, if for the remaining fences there is such i, that the height of the i-th boards vary.
As Vasily's fence can be very high and long, get the remainder after dividing the required number of ways by 1000000007 (109+7).
Input
The first line contains integer n (1≤n≤1000000)− the number of boards in Vasily's fence.
The second line contains n space-separated numbers h1,h2,...,hn (1≤hi≤109), where hi equals the height of the i-th board to the left.
Output
Print the remainder after dividing r by 1000000007, where r is the number of ways to cut exactly one connected part so that the part consisted of the upper parts of the boards and the remaining fence was good.
Examples
Input
2 1 1
Output
0
Input
3 3 4 2
Output
13
Note
From the fence from the first example it is impossible to cut exactly one piece so as the remaining fence was good.
All the possible variants of the resulting fence from the second sample look as follows (the grey shows the cut out part):
输入样例 复制
输出样例 复制