Longest Bitonic Subsequence

Interview

Time limit1sMemory limit256 MB

Summary

Given a sequence of up to 1000 numbers, find the length of its longest subsequence that strictly rises then strictly falls.

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

Problem

A sequence $S$ is bitonic if it has an element $S_k$ such that $S_1 < S_2 < \dots < S_{k-1} < S_k > S_{k+1} > \dots > S_{N-1} > S_N$ . Either the increasing part or the decreasing part may be empty, so a strictly increasing sequence and a strictly decreasing sequence are both bitonic.

For example, {10, 20, 30, 25, 20}, {10, 20, 30, 40}, {50, 40, 25, 10} are bitonic sequences, while {1, 2, 3, 2, 1, 2, 3, 2, 1} and {10, 20, 30, 40, 20, 30} are not.

Given a sequence $A$ , find the length of the longest subsequence of $A$ that is bitonic. A subsequence is what is left after deleting zero or more elements of $A$ and keeping the order of the remaining elements.

Input

The first line has the size $N$ of the sequence $A$ . The second line has $A_1, A_2, \dots, A_N$ , separated by spaces. ( $1 \le N \le 1000$ , $1 \le A_i \le 1000$ )

Output

Print on the first line the length of the longest bitonic subsequence of $A$ .

Hint

In the first example, 1, 2, 3, 4, 5, 2, 1 is a longest bitonic subsequence, and its length is 7.

Examples3

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