Пасьянс
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Иногда Рик вспоминает, что уже немолод, и предпочитает немного отдохнуть от бесконечных приключений. Одним ранним вечером, он захотел разложить пасьянс, однако обычных игральных карт у него не оказалось. Порыскав по дому Рик нашел n карточек с написанными на них натуральными числами и решил раскладывать пасьянс из них.

Так как карточки совершенно не были предназначены для пасьянса, Рик начал придумывать свои правила игры. Чтобы как-то компенсировать отсутствие цветов, Рик хочет, чтобы карточки чередовались таким образом, чтобы соседние отличались остатками при делении на два. То есть в сложенной последовательности числа на карточках должны чередоваться, например: четное, нечетное, четное и так далее... Также число на предыдущей карточке должно быть строго меньше чем число на следующей.

Рик тщательно перетасовал колоду и принялся за дело. Тем временем наблюдавший за этим Морти заинтересовался, какую максимальную последовательность карточек, удовлетворяющих условиям Рика, тот может получить из данной колоды. Ваша задача помочь ему разобраться в этом!

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

В первой строке задано целое число n — количество карточек(1 ≤ n ≤ 100).

Во второй строке задано n натуральных чисел a1, a2, ..., an — числа, написанные на карточках (1 ≤ ai ≤ 109).

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

Выведите одно число — длину максимальной последовательности, которую можно получить из данной колоды.

Примеры

Входные данные
3
1 2 3
Выходные данные
3
Входные данные
6
3 2 8 1 4 3
Выходные данные
4

Примечание

В первом примере в лучшем случае Рик будет вынимать в том же порядке, что дан. А последовательность «1, 2, 3» вполне удовлетворяет условию.

Во втором примере подойдет последовательность «1, 2, 3, 8»