Farmer John alinha $N$ vacas para uma foto ($1 \leq N \leq 50$). A altura da $i$-ésima é $a(i)$. Uma longa subsequência crescente por altura lhe parece esteticamente agradável.

Uma subsequência contém elementos $a(i_1), a(i_2), \ldots, a(i_k)$ nos índices $i_1 < i_2 < \ldots < i_k$. É crescente se $a(i_1) \leq a(i_2) \leq \ldots \leq a(i_k)$.

Para obter uma longa subsequência crescente, pode inicialmente escolher qualquer subsequência e inverter seus elementos.

Por exemplo, na lista

1 6 2 3 4 3 5 3 4

podemos inverter os elementos escolhidos

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

para obter

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

A subsequência invertida ocupa os mesmos índices, deixando os outros elementos iguais.

Encontre o maior comprimento possível de uma subsequência crescente ao inverter uma subsequência arbitrária uma vez.

Entrada

Leia da entrada padrão.

A primeira linha contém $N$. As outras $N$ contêm $a(1) \ldots a(N)$, inteiros em $1 \ldots 50$.

Saída

Escreva na saída padrão.

Imprima o número de elementos da maior subsequência crescente possível após inverter no máximo uma subsequência.

Exemplos

Entrada 1

9
1
2
3
9
5
6
8
7
4

Saída 1

9

Créditos do problema: Lewin Gan