The Mountain Subsequence

Difficulty: 1600 6000 ms 128 MB

dp

A bitonic subsequence strictly increases and then strictly decreases (either side may be length 1). Print the length of the longest bitonic subsequence.

Input: the first line has N; the second line has N integers.

Output: the longest bitonic subsequence length.

Constraints:

• 1 ≤ N ≤ 5000 (tests use N ≤ 1500)
• |a_i| ≤ 10⁹

Sample Tests

7
1 4 2 3 5 4 1

6

1
9

1

Read the Editorial