시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 1024 MB147949167.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:

  • $(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점)

This subtask has additional constraints: 

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

서브태스크 2 (5점)

This subtask has an additional constraint: 

  • $N \le 3$

서브태스크 3 (10점)

This subtask has an additional constraint:  

  • $h_1 = h_2 = \cdots = h_N$

서브태스크 4 (15점)

This subtask has an additional constraint:

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

서브태스크 5 (60점)

This subtask has no additional constraints. 

예제 입력 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

출처

University > KAIST > 2021 KAIST RUN Spring Contest B번

채점 및 기타 정보

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