Урок физкультуры

시간 제한2초메모리 제한1024 MB

요약

수열을 연속한 구간들로 나누되 각 구간이 비감소 또는 비증가가 되도록 하는 분할의 수를 10^9+7로 나눈 나머지로 구합니다.

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

문제

На очередном уроке физкультуры Фома придумал интересное занятие.

После того как школьники выстроились в шеренгу, он дал каждому свой персональный номер. Теперь он просит школьников разбится на группы, чтобы выполнялись условия:

Каждая группа --- это подотрезок шеренги. То есть школьники в группе стоят в шеренге подряд.
Группы не пересекаются.
В каждой группе последовательность персональных номеров школьников либо нестрого возрастает, либо нестрого убывает.

Перебрав несколько способов, Фома заинтересовался, сколько их может быть всего. Он просит вас написать программу, которая вычислит, сколько есть способов разбиения школьников на такие группы.

입력

В первой строке входного файла задано число $n$ ( $1 \le n \le 5000$ ) --- количество школьников. Во второй строке содержатся $n$ чисел $a\_1, a\_2, \ldots, a\_n$ ( $1 \le a\_i \le 10^9$ ) --- персональный номер каждого школьника.

출력

В единственной строке выходного файла выведите одно число --- количество способов разделить школьников на группы. Ответ может быть очень большой, поэтому нужно вывести его по модулю $10^9+7$ .

예제3

예제 1
입력
```
4
1 2 3 4
```
예상 출력
```
8
```
예제 2
입력
```
5
1 2 2 2 1
```
예상 출력
```
15
```
예제 3
입력
```
5
1 2 1 2 1
```
예상 출력
```
8
```