Farmer John ustawia $N$ krów do zdjęcia ($1 \leq N \leq 50$). Wysokość $i$-tej to $a(i)$. Długi podciąg rosnący według wysokości uczyni zdjęcie ładnym.

Podciąg to elementy $a(i_1), a(i_2), \ldots, a(i_k)$ na indeksach $i_1 < i_2 < \ldots < i_k$. Jest rosnący, jeśli $a(i_1) \leq a(i_2) \leq \ldots \leq a(i_k)$.

Dla długiego podciągu rosnącego może początkowo wybrać dowolny podciąg i odwrócić jego elementy.

Na przykład w liście

1 6 2 3 4 3 5 3 4

możemy odwrócić wybrane elementy

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

i otrzymać

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

Odwrócony podciąg zajmuje te same indeksy, pozostałe elementy nie zmieniają się.

Znajdź największą długość podciągu rosnącego, gdy wolno raz odwrócić dowolny podciąg.

Wejście

Czytaj ze standardowego wejścia.

Pierwszy wiersz zawiera $N$. Pozostałe $N$ zawiera $a(1) \ldots a(N)$, całkowite w $1 \ldots 50$.

Wyjście

Pisz na standardowe wyjście.

Wypisz liczbę elementów najdłuższego możliwego podciągu rosnącego po odwróceniu najwyżej jednego podciągu.

Przykład

Wejście 1

9
1
2
3
9
5
6
8
7
4

Wyjście 1

9

Autor zadania: Lewin Gan