Taco: Maximum Buildings in Subsequences

You are given a sequence of ( n ) buildings with their heights. The task is to determine the maximum total number of buildings that can be captured by choosing an index ( i ) (where ( 0 \le i \le n )) and forming two subsequences: a non-decreasing subsequence from the left part (i.e. from the first building to the ( (i-1))th building) and a non-increasing subsequence from the right part (i.e. from the ( i )th building to the last building). Formally, if you split the array into two parts ( A = a_1, a_2, \ldots, a_i ) and ( B = a_{i+1}, a_{i+2}, \ldots, a_n ), you need to find the maximum value of ( LND(A) + LNI(B) ), where ( LND(A) ) is the length of a longest non-decreasing subsequence in ( A ) and ( LNI(B) ) is the length of a longest non-increasing subsequence in ( B ).

Note: A subsequence is obtained by deleting some (or no) elements without changing the order of the remaining elements. The non-decreasing subsequence satisfies ( x_1 \le x_2 \le \cdots ), while the non-increasing one satisfies ( y_1 \ge y_2 \ge \cdots ).

inputFormat

The first line contains an integer ( n ) denoting the number of buildings. The second line contains ( n ) space-separated integers representing the heights of the buildings.

outputFormat

Output a single integer: the maximum total number of buildings that can be included in the two subsequences when splitting the array optimally.## sample

6
5 1 3 4 2 1

5