Codeforces Round 346 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

combinatorics

dp

number theory

*2300

No tag edit access

The problem statement has recently been changed. View the changes.

×
G. Fence Divercity

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputLong 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 *h*_{i}.

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 1 000 000 007 (10^{9} + 7).

Input

The first line contains integer *n* (1 ≤ *n* ≤ 1 000 000) — the number of boards in Vasily's fence.

The second line contains *n* space-separated numbers *h*_{1}, *h*_{2}, ..., *h*_{n} (1 ≤ *h*_{i} ≤ 10^{9}), where *h*_{i} equals the height of the *i*-th board to the left.

Output

Print the remainder after dividing *r* by 1 000 000 007, 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):

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/03/2023 18:39:05 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|