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