Subsequence Reversal#10555

Subsequence Reversal

1 second

128 megabytes

Very hard

Farmer John is arranging his $n$ cows in a line to take a photo. The height of the $i$ -th cow in the lineup is $a_{i}$ a_i, and Farmer John thinks the photo would look more aesthetically pleasing if the lineup contained a long increasing subsequence of cows by height.

Recall that a subsequence is a sequence of elements $a_{i_{1}}, a_{i_{2}}, \dots, a_{i_{k}}$ a_{i_1}, a_{i_2}, \ldots, a_{i_k} from the original sequence, where the corresponding indices satisfy $i_{1} < i_{2} < \dots < i_{k}$ i_1 < i_2 < \ldots < i_k. We say that the subsequence is increasing if $a_{i_{1}} \leq a_{i_{2}} \leq \dots \leq a_{i_{k}}$ a_{i_1} \le a_{i_2} \le \ldots \le a_{i_k}.

FJ would like his lineup to contain a long increasing subsequence. To help achieve this, he may choose any subsequence of the cows and reverse the order of its elements.

For example, suppose the lineup is

1 6 2 3 4 3 5 3 4

We can choose the elements marked below:

1 6 2 3 4 3 5 3 4
  ^         ^ ^ ^

and reverse their order to obtain

1 4 2 3 4 3 3 5 6
  ^         ^ ^ ^

Notice that the reversed elements occupy exactly the same set of positions as before, while all other elements remain unchanged.

Determine the maximum possible length of an increasing subsequence after reversing the elements of at most one subsequence.

Input

The first line contains $n (1 \leq n \leq 50)$ n~(1 \le n \le 50). The next $n$ lines contain $a_{1}, \dots, a_{n}$ a_1, \ldots, a_n, where each $a_{i}$ a_i is an integer in the range $1 \dots 50$ .

Output

Print the maximum possible length of an increasing subsequence after reversing the elements of at most one subsequence.

Examples

Example 1