Longest Bitonic Subsequence

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.

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$)

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

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