Physical Education Class

Interview

Time limit2sMemory limit1024 MB

Summary

Count the ways to split a row of n numbers into contiguous groups, each non-decreasing or non-increasing, modulo 1e9+7.

Level: Medium5 of 10
Topics: Dynamic programming, Array
Solved: No attempts yet

Problem

During a physical education class, Foma came up with an interesting activity.

After the schoolchildren lined up in a row, he gave each of them a personal number. Now he asks the children to split into groups so that the following conditions hold:

Each group is a contiguous segment of the row. That is, the children in a group stand next to each other in the row.
Groups do not overlap.
In each group, the sequence of personal numbers is either non-decreasing or non-increasing.

After trying several ways, Foma became curious how many ways there are in total. He asks you to write a program that counts the number of ways to split the schoolchildren into such groups.

Input

The first line contains the number $n$ ( $1 \le n \le 5000$ ) of schoolchildren. The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $1 \le a_i \le 10^9$ ), the personal number of each schoolchild.

Output

Print one number, the number of ways to split the schoolchildren into groups. The answer can be very large, so print it modulo $10^9+7$ .

Examples3

Example 1
Input
```
4
1 2 3 4
```
Expected output
```
8
```
Example 2
Input
```
5
1 2 2 2 1
```
Expected output
```
15
```
Example 3
Input
```
5
1 2 1 2 1
```
Expected output
```
8
```