Farmer John aligne $N$ vaches pour une photo ($1 \leq N \leq 50$). La taille de la $i$-ième est $a(i)$. Il trouve la photo plus belle avec une longue sous-séquence croissante de tailles.

Une sous-séquence est un ensemble d’éléments $a(i_1), a(i_2), \ldots, a(i_k)$ aux indices $i_1 < i_2 < \ldots < i_k$. Elle est croissante si $a(i_1) \leq a(i_2) \leq \ldots \leq a(i_k)$.

Pour obtenir une longue sous-séquence croissante, il peut initialement choisir une sous-séquence quelconque et inverser ses éléments.

Par exemple, avec la liste

1 6 2 3 4 3 5 3 4

on peut inverser les éléments choisis

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

pour obtenir

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

La sous-séquence inversée conserve les mêmes indices et les autres éléments restent inchangés.

Trouvez la longueur maximale possible d’une sous-séquence croissante en inversant une sous-séquence arbitraire une fois.

Entrée

Lisez l’entrée standard.

La première ligne contient $N$. Les $N$ restantes contiennent $a(1) \ldots a(N)$, entiers dans $1 \ldots 50$.

Sortie

Écrivez sur la sortie standard.

Affichez le nombre d’éléments de la plus longue sous-séquence croissante possible après avoir inversé au plus une sous-séquence.

Exemples

Entrée 1

9
1
2
3
9
5
6
8
7
4

Sortie 1

9

Auteur du problème : Lewin Gan