Longest Bitonic Subsequence

You are given an array of n positive integers. Your task is to find the length of the longest bitonic subsequence.

A subsequence is called bitonic if there exists an index i (1 ≤ i ≤ k) such that:

That is, the subsequence first strictly increases and then strictly decreases. Note that a strictly increasing or strictly decreasing subsequence is considered bitonic as well.

Your program should read the input from standard input (stdin) and print the result to standard output (stdout).

inputFormat

The input consists of two lines:

1. The first line contains a single integer n (0 ≤ n ≤ 10^5), representing the number of elements in the array.
2. The second line contains n space-separated integers, representing the elements of the array.

outputFormat

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

8
1 11 2 10 4 5 2 1

6