Longest Bitonic Subsequence

Given an array of n integers, a subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order. A sequence is called bitonic if it first strictly increases and then strictly decreases.

Your task is to compute the length of the longest bitonic subsequence. Mathematically, the answer is given by:

$$\max_{0 \leq i < n}\big(\text{LIS}(i) + \text{LDS}(i) - 1\big)$$

where \(\text{LIS}(i)\) is the length of the longest increasing subsequence ending at index i, and \(\text{LDS}(i)\) is the length of the longest decreasing subsequence starting at index i.

inputFormat

The input is read from stdin:

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

outputFormat

Output to stdout a single integer representing the length of the longest bitonic subsequence.## sample

8
1 11 2 10 4 5 2 1

6