Fence Divercity

题意翻译

 $Vasily$有一个栅栏，你可以将它看做由 $n$ 个垂直的木板组成。每个木板的宽为 $1$ 个单位，从左到右第 $i$ 块木板高为 $hi$ 个单位。现在这些木板都是彼此相连构成了一个完整的栅栏。  由于$Vasily$厌倦了这种布局，他希望将某些木板砍去一部分。要求满足以下限制条件：  1.砍去的部分只能是木板的上部。(否则栅栏就立不起来了)  2.砍去的部分必须相连（只有上下左右四个方向算相连，左上角等不算相连）。  3.每块木板只能砍去整数单位的高度和$1$个单位的宽度。  4.不能将某块木板全部砍去，即每块木板至少保留$1$个单位的高度。（这样才能保证剩余的木板依旧能构成一个完整的栅栏）  现在$Vasily$想知道他有多少种砍的方案。由于这个数可能很大，你需要输出它对 $1000000007$ 取模后的答案。 ### 输入描述  第一行一个整数$n$。接下来一行$n$个整数。第$i$个整数表示 $hi$。 ### 输出描述  输出一个整数表示方案数对$1000000007$取模后的答案。 ### 样例解释  对于第一个样例，由于条件 4 的限制所以没有满足条件的方案。对于第二个样例，满足条件的 13 种方案如下: 

题目描述

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 $ 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 $ 1000000007 $ $ (10^{9}+7) $ .

输入输出格式

输入格式

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

输出格式

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.

输入输出样例

输入样例 #1

2
1 1

输出样例 #1

0

输入样例 #2

3
3 4 2

输出样例 #2

13

说明

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):