패션스

가끔 릭은 자신이 이제 젊지 않다는 것을 떠올리고, 끝없는 모험에서 벗어나 쉬는 편을 택한다. 어느 이른 저녁, 그는 패션스를 하고 싶었지만 일반 카드가 없었다. 집안을 뒤진 릭은 자연수가 적힌 카드 $n$장을 찾아 이것으로 패션스를 하기로 했다.

카드는 패션스용으로 만들어진 것이 아니었기 때문에 릭은 직접 규칙을 만들었다. 무늬가 없는 점을 보완하려고 릭은 카드가 번갈아 놓이기를 원한다. 인접한 두 카드의 수를 2로 나눈 나머지가 서로 달라야 한다. 즉 펼친 순서에서 수가 짝수, 홀수, 짝수처럼 번갈아 나와야 한다. 또한 앞 카드의 수는 뒤 카드의 수보다 엄격히 작아야 한다.

릭은 덱을 꼼꼼히 섞고 게임을 시작했다. 이를 지켜보던 모티는 이 덱에서 릭의 조건을 만족하는 가장 긴 카드 열이 얼마나 긴지 궁금해졌다. 그 길이를 구하도록 도와라.

첫 번째 줄에 카드의 개수를 나타내는 정수 $n$ ($1 \le n \le 100$)이 주어진다.

두 번째 줄에는 카드에 적힌 자연수 $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$)이 주어진다.

주어진 덱에서 만들 수 있는 가장 긴 카드 열의 길이를 한 줄에 출력한다.

첫 번째 예시에서 릭이 가장 좋은 경우에 주어진 순서대로 카드를 뽑는다. 수열 $1, 2, 3$은 조건을 만족한다.

두 번째 예시에서는 수열 $1, 2, 3, 8$이 적합하다.