시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 1024 MB137868366.935%

## 문제

A 2-dimensional grid can be represented as a set of pairs of positive integers. Each cell can be numbered as in the figure below: Suppose you are given a histogram where the height of each column is $h_1, h_2, \cdots, h_N$. Its area can be represented as a set containing cells $(i, 1), (i, 2), \cdots, (i, h_i)$ for $i = 1, 2, \cdots, N$. (If $h_i = 0$, it means the histogram's area does not contain any cell from the $i$-th column.)

You may choose $N$ integers $x_1, x_2, \cdots, x_N$ with $0 \le x_i < h_i$ and subtract a sub-histogram with heights $x_1, x_2, \cdots, x_N$. After removing such a sub-histogram, the remaining area can be written as: $$\bigcup_{i=1}^N \{ (i, j) : x_i < j \le h_i \}.$$

For example, the following figure shows an example of $h_1 = 4$, $h_2 = 5$, $h_3 = 4$, $h_4 = 4$ and $x_1 = 1$, $x_2 = 2$, $x_3 = 3$, $x_4 = 2$. The remaining area is called connected if for every pair of cells $((r_1, c_1), (r_2, c_2))$ in the remaining area, one can move from $(r_1, c_1)$ to $(r_2, c_2)$ using only the following moves without leaving the remaining area:

• $(r, c) \to (r+1, c)$
• $(r, c) \to (r-1, c)$
• $(r, c) \to (r, c+1)$
• $(r, c) \to (r, c-1)$

Compute the number of ways to choose $(x_1, x_2, \cdots, x_N)$ such that the remaining area is connected.

## 입력

The first line contains a single integer, $N$. The second line contains $N$ integers - $h_1, h_2, \cdots, h_N$ in order.

## 출력

Output the number of ways to choose $(x_1, x_2, \cdots, x_N)$ such that the remaining area is connected, modulo $10^9 + 7$.

## 제한

• $1 \le N \le 250\,000$
• $1 \le h_i \le 10^9$

## 서브태스크 1 (10점)

• $N \le 3$
• $h_i \le 100$ for $i = 1, 2, \cdots, N$

## 서브태스크 2 (5점)

• $N \le 3$

## 서브태스크 3 (10점)

• $h_1 = h_2 = \cdots = h_N$

## 서브태스크 4 (15점)

• $h_1 \le h_2 \le \cdots \le h_N$

## 예제 입력 1

1
100


## 예제 출력 1

100


## 예제 입력 2

3
2 3 4


## 예제 출력 2

12


## 예제 입력 3

3
100 100 100


## 예제 출력 3

1000000


## 예제 입력 4

2
100000 100000


## 예제 출력 4

999999937


## 예제 입력 5

2
3 42


## 예제 출력 5

9


## 예제 입력 6

3
1 1 1


## 예제 출력 6

1


## 채점 및 기타 정보

• 예제는 채점하지 않는다.