## USACO 2017 January Contest, Platinum

## Problem 3. Subsequence Reversal

Contest has ended.

**Log in to allow submissions in analysis mode**

To recall, a subsequence is a subset $a(i_1), a(i_2), \ldots, a(i_k)$ of elements from the cow sequence, found at some series of indices $i_1 < i_2 < \ldots < i_k$. We say the subsequence is increasing if $a(i_1) \leq a(i_2) \leq \ldots \leq a(i_k)$.

FJ would like there to be a long increasing subsequence within his ordering of the cows. In order to ensure this, he allows himself initially to choose any subsequence and reverse its elements.

For example, if we had the list

1 6 2 3 4 3 5 3 4

We can reverse the chosen elements

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

to get

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

Observe how the subsequence being reversed ends up using the same indices as it initially occupied, leaving the other elements unchanged.

Please find the maximum possible length of an increasing subsequence, given that you can choose to reverse an arbitrary subsequence once.

#### INPUT FORMAT (file subrev.in):

The first line of input contains $N$. The remaining $N$ lines contain $a(1) \ldots a(N)$, each an integer in the range $1 \ldots 50$.#### OUTPUT FORMAT (file subrev.out):

Output the number of elements that can possibly form a longest increasing subsequence after reversing the contents of at most one subsequence.#### SAMPLE INPUT:

9 1 2 3 9 5 6 8 7 4

#### SAMPLE OUTPUT:

9

Problem credits: Lewin Gan