감소하는 점열

시간 제한1초메모리 제한256 MB

요약

대각선 x+y=a_i 위의 격자점으로 x는 감소하지 않고 y는 증가하지 않게 이어지는 수열 개수를 구합니다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 누적 합
정답자: 아직 제출이 없습니다

문제

좌표가 음이 아닌 정수인 서로 다른 점 $A_1(x_1, y_1), A_2(x_2, y_2), \ldots, A_n(x_n, y_n)$ 이 주어진다. 임의의 $i$ 에 대해 $x_i \le x_{i+1}$ 이고 $y_i \ge y_{i+1}$ 이면 이 점열을 감소한다고 한다.

$x_1 + y_1 = a_1, x_2 + y_2 = a_2, \ldots, x_n + y_n = a_n$ 을 만족하는 감소 점열의 개수를 구하라.

입력

첫 줄에 양의 정수 $n$ 이 주어진다. 둘째 줄에 $n$ 개의 음이 아닌 정수 $a_1, a_2, \ldots, a_n$ 이 주어진다.

출력

조건을 만족하는 점열의 개수를 $123456789$ 로 나눈 나머지를 출력한다.

제한

$n \le 10000$
$0 \le a_i \le 10000$
$a_i \ne a_{i+1}$

예제6

예제 1
입력
```
3
4 5 3
```
예상 출력
```
10
```
예제 2
입력
```
1
0
```
예상 출력
```
1
```
예제 3
입력
```
1
5
```
예상 출력
```
6
```
예제 4
입력
```
2
1 2
```
예상 출력
```
3
```
예제 5
입력
```
2
3 7
```
예상 출력
```
10
```
예제 6
입력
```
4
1 2 3 4
```
예상 출력
```
5
```