Group Jump Rope

Interview

Time limit1sMemory limit1024 MB

Summary

Given student heights, find the largest group that can line up so heights strictly rise toward the middle and then strictly fall, so no one faces someone as tall or taller.

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

Problem

$N$ students want to jump rope together. They must stand in a single line, and each student faces one of the two ends of the line.

A student can get caught by the rope if someone in the direction they face is as tall as them or taller. Students want to jump as many times as possible, so they avoid situations where the rope can catch them. Each student lines up so that everyone in the direction they face is shorter than them.

Given the heights of the students, find the maximum number of students who can take part in the group jump rope. The person turning the rope is not included among the students.

Input

The first line contains the number of students $N$ . ( $1 \leq N \leq 1\,000$ )

The second line contains the heights $A_i$ of the students, separated by spaces. ( $1 \leq A_i \leq 1\,000$ )

Output

Print the maximum number of students who can take part in the group jump rope when the students are arranged so that no one can get caught on the rope.

Examples3

Example 1
Input
```
5
1 2 3 4 5
```
Expected output
```
5
```
Example 2
Input
```
10
1 3 2 4 2 4 4 3 2 7
```
Expected output
```
8
```
Example 3
Input
```
5
10 10 10 10 10
```
Expected output
```
2
```