시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 12 7 6 75.000%

문제

상근이의 여동생 선영이는 정인이가 상근이의 마이크로프로세서를 훔치는 것을 보았다. 선영이는 상근이에게 이 사실을 말해야 하는지를 고민했다. 하지만, 선영이는 상근이보다 정인이를 더 좋아하기 때문에 말하지 않았다.

선영이는 정인이에게 데이트 신청을 하였고, 영화를 같이 보러간다면 이 사실을 그 누구에게도 말하지 않기로 약속했다.

알고보니 정인이는 여자에게 별 관심이 없었다. 그 이유는 정인이가 수학문제를 푸는데 방해 된다고 생각하기 때문이다. 따라서, 그는 선영이에게 게임을 신청했고, 이기면 영화를 보러 가기로 했다. 선영이는 게임에 자신이 있었기 때문에, 정인이의 제안에 동의했다.

정인이는 N개의 양수를 원 위에 차례대로 쓰고 선영이에게 게임의 규칙을 설명했따.

1. 첫 번째 플레이어가 아무 숫자나 하나 고른다.

2. 두 번째 플레이어가 첫 번째 플레이어가 고른 수에 인접한 두 수 중 하나를 고른다.

3. 그 다음 플레이어는 고를 수 있는 수가 없을 때까지 지금까지 고른 수에 인접한 수 중에서 아무 숫자나 고른다. 홀수를 가장 많이 고른 사람이 승리한다.

정인이는 최선을 다해서 게임을 한다. 그는 항상 이기거나 비길 수 있는 전략을 선택한다. 정인이는 선영이가 게임을 얼마나 잘 하는지 모른다. 또, 정인이는 신사이기 때문에, 선영이에게 첫 번째 수를 양보했다.

선영이가 게임을 승리하기 위해서 고를 수 있는 첫 번째 수의 총 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 원 위에 있는 수의 개수 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄에는 N개의 정수가 공백으로 구분되어 주어진다. 모든 숫자는 1 이상 1000 이하이다. 두 수가 같은 경우는 없다.

출력

선영이가 게임을 승리하기 위해서 고를 수 있는 첫 번째 수의 개수를 첫째 줄에 출력한다.

예제 입력

3
3 1 5

예제 출력

3

힌트