Longest Bitonic Subsequence

Given a sequence of integers, your task is to determine the length of the longest bitonic subsequence. A bitonic sequence is one that first strictly increases and then strictly decreases. Formally, a sequence a₁, a₂, ..., a_n is bitonic if there exists an index k (1 ≤ k ≤ n) such that:

\(a_1 < a_2 < \cdots a_{k+1} > \cdots > a_n\)

If the sequence is empty, the output should be 0.

This problem can be effectively solved using dynamic programming by computing, for each index, the length of the longest increasing subsequence ending at that index and the length of the longest decreasing subsequence starting from that index. The answer is then the maximum value of (increasing_length + decreasing_length - 1) over all indices.

inputFormat

The input is given via standard input (stdin). The first line contains an integer n, representing the number of elements in the sequence. If n > 0, the second line contains n space-separated integers denoting the sequence.

outputFormat

Output a single integer to standard output (stdout), which is the length of the longest bitonic subsequence.## sample

6
1 2 5 3 2 1

6