시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 1024 MB | 147 | 94 | 91 | 67.910% |
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:
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$.
This subtask has additional constraints:
This subtask has an additional constraint:
This subtask has an additional constraint:
This subtask has an additional constraint:
This subtask has no additional constraints.
1 100
100
3 2 3 4
12
3 100 100 100
1000000
2 100000 100000
999999937
2 3 42
9
3 1 1 1
1