Longest Bitonic Subsequence

You are given an array of n integers. Your task is to compute the length of the longest bitonic subsequence in the array. A bitonic subsequence is a sequence that first strictly increases and then strictly decreases. Note that either the increasing or decreasing part can be empty (but not both simultaneously), meaning a strictly increasing or strictly decreasing sequence is considered as a valid bitonic subsequence.

The problem can be formulated as follows: Given an integer n and an array A of n integers, find the maximum length L such that there exists indices 1 ≤ i₁ < i₂ < ... < i_L with the property that for some index k (1 ≤ k ≤ L),

[ a_{i_1} < a_{i_2} < \cdots < a_{i_k} \quad\text{and}\quad a_{i_k} > a_{i_{k+1}} > \cdots > a_{i_L} ]

If the array size is zero, return 0.

inputFormat

The input is given from stdin as follows:

1. The first line contains a single integer n, representing the number of elements in the array.
2. The second line contains n space-separated integers, representing the elements of the array. If n is 0, the second line may be empty.

outputFormat

Output a single integer to stdout, which is the length of the longest bitonic subsequence in the given array.

6
1 4 2 8 3 2

5