Longest Bitonic Subsequence

Given a sequence of n integers, find the length of the longest bitonic subsequence. A bitonic subsequence is a sequence which first increases and then decreases. Note that a strictly increasing or strictly decreasing sequence is considered bitonic as well.

Let the input sequence be \(a_1, a_2, \dots, a_n\). We define two arrays:

• \(inc[i]\): the length of the longest increasing subsequence ending at index \(i\).
• \(dec[i]\): the length of the longest decreasing subsequence starting at index \(i\).

The answer is \(\max_{1 \le i \le n} \{inc[i] + dec[i] - 1\}\).

Your task is to compute this maximum value.

inputFormat

The input is given on two lines. The first line contains a single integer (n) ((1 \le n \le 10^5)), the length of the sequence. The second line contains (n) space-separated integers representing the sequence.

outputFormat

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

1
1

1