Farmer John выстраивает $N$ коров для фото ($1 \leq N \leq 50$). Высота $i$-й — $a(i)$. Он считает, что длинная возрастающая по высоте подпоследовательность сделает фото красивым.

Подпоследовательность — элементы $a(i_1), a(i_2), \ldots, a(i_k)$ на индексах $i_1 < i_2 < \ldots < i_k$. Она возрастающая, если $a(i_1) \leq a(i_2) \leq \ldots \leq a(i_k)$.

Для длинной возрастающей подпоследовательности он может сначала выбрать любую подпоследовательность и развернуть её элементы.

Например, для списка

1 6 2 3 4 3 5 3 4

можно развернуть выбранные элементы

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

и получить

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

Развёрнутая подпоследовательность занимает те же индексы, прочие элементы неизменны.

Найдите максимальную длину возрастающей подпоследовательности, если разрешён один разворот произвольной подпоследовательности.

Входные данные

Читайте стандартный ввод.

Первая строка содержит $N$. Остальные $N$ содержат $a(1) \ldots a(N)$, целые в диапазоне $1 \ldots 50$.

Выходные данные

Пишите в стандартный вывод.

Выведите число элементов максимально длинной возрастающей подпоследовательности после разворота не более одной подпоследовательности.

Примеры

Входные данные 1

9
1
2
3
9
5
6
8
7
4

Выходные данные 1

9

Автор задачи: Lewin Gan