시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB56403670.588%

문제

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

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

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

입력

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

Во второй строке задано $n$ натуральных чисел $a_1, a_2, \ldots, a_n$ --- числа, написанные на карточках ($1 \le a_i \le 10^9$).

출력

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

예제 입력 1

3
1 2 3

예제 출력 1

3

예제 입력 2

6
3 2 8 1 4 3

예제 출력 2

4

노트

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

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