Solitaire

Sometimes Rick remembers that he is no longer young and prefers to rest from endless adventures. One early evening he wanted to play solitaire, but he had no ordinary playing cards. After searching the house, Rick found $n$ cards with natural numbers written on them and decided to build a solitaire layout from them.

Since the cards were not made for solitaire, Rick invented his own rules. To make up for the lack of suits, he wants the cards to alternate so that adjacent cards have different remainders when divided by two. In the laid-out sequence the numbers must alternate as even, odd, even, and so on. Also, the number on each card must be strictly less than the number on the next card.

Rick shuffled the deck carefully and started playing. Morty, watching him, wondered what is the longest sequence of cards that satisfies Rick's conditions that can be taken from this deck. Help him find out.

The first line contains an integer $n$ ($1 \le n \le 100$), the number of cards.

The second line contains $n$ natural numbers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$), the numbers written on the cards.

Print one number, the length of the longest sequence that can be obtained from the given deck.

In the first sample, in the best case Rick draws the cards in the same order as given. The sequence $1, 2, 3$ satisfies the condition.

In the second sample, the sequence $1, 2, 3, 8$ fits.