Longest Bitonic Subsequence

Given an array of integers, a bitonic subsequence is defined as a sequence that first increases and then decreases. Formally, a sequence B is bitonic if there exists an index k such that:

$$ B_1 < B_2 < \cdots < B_k \quad\text{and}\quad B_k > B_{k+1} > \cdots > B_n $$

Your task is to find the length of the longest bitonic subsequence in the given array. Note that a strictly increasing or strictly decreasing subsequence is also considered a bitonic subsequence.

Example:

Input: 8
       1 11 2 10 4 5 2 1
Output: 6

The longest bitonic subsequence in the above example is [1, 11, 10, 4, 2, 1] with a length of 6.

inputFormat

The first line contains a single integer n denoting the number of elements in the array. The second line contains n space-separated integers representing the elements of the array.

Input is provided via standard input (stdin).

outputFormat

Output a single integer denoting the length of the longest bitonic subsequence. Output should be written to standard output (stdout).

## sample

8
1 11 2 10 4 5 2 1

6

</p>