28858번 - Пасьянс 다국어

문제

Иногда Рик вспоминает, что уже немолод, и предпочитает немного отдохнуть от бесконечных приключений. Одним ранним вечером, он захотел разложить пасьянс, однако обычных игральных карт у него не оказалось. Порыскав по дому Рик нашел $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>>