Пасьянс

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

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

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

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

Во второй строке задано $n$ натуральных чисел $a\_1, a\_2, \ldots, a\_n$ --- числа, написанные на карточках ($1 \le a\_i \le 10^9$).

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

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

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