시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB2391058450.299%

문제

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

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

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

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

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

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

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

입력

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

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

출력

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

예제 입력 1

3
3 1 5

예제 출력 1

3

예제 입력 2

4
1 2 3 4

예제 출력 2

2

예제 입력 3

8
4 10 5 2 9 8 1 7

예제 출력 3

5
W3sicHJvYmxlbV9pZCI6IjMwMzIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyYjlcdWI5YWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1Yzc1OCBcdWM1ZWNcdWIzZDlcdWMwZGQgXHVjMTIwXHVjNjAxXHVjNzc0XHViMjk0IFx1YzgxNVx1Yzc3OFx1Yzc3NFx1YWMwMCBcdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHViOWM4XHVjNzc0XHVkMDZjXHViODVjXHVkNTA0XHViODVjXHVjMTM4XHVjMTFjXHViOTdjIFx1ZDZkNFx1Y2U1OFx1YjI5NCBcdWFjODNcdWM3NDQgXHViY2Y0XHVjNTU4XHViMmU0LiBcdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNWQwXHVhYzhjIFx1Yzc3NCBcdWMwYWNcdWMyZTRcdWM3NDQgXHViOWQwXHVkNTc0XHVjNTdjIFx1ZDU1OFx1YjI5NFx1YzljMFx1Yjk3YyBcdWFjZTBcdWJiZmNcdWQ1ODhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHVjMTIwXHVjNjAxXHVjNzc0XHViMjk0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YmNmNFx1YjJlNCBcdWM4MTVcdWM3NzhcdWM3NzRcdWI5N2MgXHViMzU0IFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHViOWQwXHVkNTU4XHVjOWMwIFx1YzU0YVx1YzU1OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMTIwXHVjNjAxXHVjNzc0XHViMjk0IFx1YzgxNVx1Yzc3OFx1Yzc3NFx1YzVkMFx1YWM4YyBcdWIzNzBcdWM3NzRcdWQyYjggXHVjMmUwXHVjY2FkXHVjNzQ0IFx1ZDU1OFx1YzYwMFx1YWNlMCwgXHVjNjAxXHVkNjU0XHViOTdjIFx1YWMxOVx1Yzc3NCBcdWJjZjRcdWI3ZWNcdWFjMDRcdWIyZTRcdWJhNzQgXHVjNzc0IFx1YzBhY1x1YzJlNFx1Yzc0NCBcdWFkZjggXHViMjA0XHVhZDZjXHVjNWQwXHVhYzhjXHViM2M0IFx1YjlkMFx1ZDU1OFx1YzljMCBcdWM1NGFcdWFlMzBcdWI4NWMgXHVjNTdkXHVjMThkXHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NGNcdWFjZTBcdWJjZjRcdWIyYzggXHVjODE1XHVjNzc4XHVjNzc0XHViMjk0IFx1YzVlY1x1Yzc5MFx1YzVkMFx1YWM4YyBcdWJjYzQgXHVhZDAwXHVjMmVjXHVjNzc0IFx1YzVjNlx1YzVjOFx1YjJlNC4gXHVhZGY4IFx1Yzc3NFx1YzcyMFx1YjI5NCBcdWM4MTVcdWM3NzhcdWM3NzRcdWFjMDAgXHVjMjE4XHVkNTU5XHViYjM4XHVjODFjXHViOTdjIFx1ZDQ3OFx1YjI5NFx1YjM3MCBcdWJjMjlcdWQ1NzQgXHViNDFjXHViMmU0XHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHVhZGY4XHViMjk0IFx1YzEyMFx1YzYwMVx1Yzc3NFx1YzVkMFx1YWM4YyBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjMmUwXHVjY2FkXHVkNTg4XHVhY2UwLCBcdWM3NzRcdWFlMzBcdWJhNzQgXHVjNjAxXHVkNjU0XHViOTdjIFx1YmNmNFx1YjdlYyBcdWFjMDBcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LiBcdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHVhYzhjXHVjNzg0XHVjNWQwIFx1Yzc5MFx1YzJlMFx1Yzc3NCBcdWM3ODhcdWM1YzhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWM4MTVcdWM3NzhcdWM3NzRcdWM3NTggXHVjODFjXHVjNTQ4XHVjNWQwIFx1YjNkOVx1Yzc1OFx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODE1XHVjNzc4XHVjNzc0XHViMjk0IE5cdWFjMWNcdWM3NTggXHVjNTkxXHVjMjE4XHViOTdjIFx1YzZkMCBcdWM3MDRcdWM1ZDAgXHVjYzI4XHViODQwXHViMzAwXHViODVjIFx1YzRmMFx1YWNlMCBcdWMxMjBcdWM2MDFcdWM3NzRcdWM1ZDBcdWFjOGMgXHVhYzhjXHVjNzg0XHVjNzU4IFx1YWRkY1x1Y2U1OVx1Yzc0NCBcdWMxMjRcdWJhODVcdWQ1ODhcdWI1MzAuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWFjMDAgXHVjNTQ0XHViYjM0IFx1YzIyYlx1Yzc5MFx1YjA5OCBcdWQ1NThcdWIwOTggXHVhY2UwXHViOTc4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWI0NTAgXHViYzg4XHVjOWY4IFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1YWMwMCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1YWMwMCBcdWFjZTBcdWI5NzggXHVjMjE4XHVjNWQwIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWI0NTAgXHVjMjE4IFx1YzkxMSBcdWQ1NThcdWIwOThcdWI5N2MgXHVhY2UwXHViOTc4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWFkZjggXHViMmU0XHVjNzRjIFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1YjI5NCBcdWFjZTBcdWI5N2MgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMyMThcdWFjMDAgXHVjNWM2XHVjNzQ0IFx1YjU0Y1x1YWU0Y1x1YzljMCBcdWM5YzBcdWFlMDhcdWFlNGNcdWM5YzAgXHVhY2UwXHViOTc4IFx1YzIxOFx1YzVkMCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHVjMjE4IFx1YzkxMVx1YzVkMFx1YzExYyBcdWM1NDRcdWJiMzQgXHVjMjJiXHVjNzkwXHViMDk4IFx1YWNlMFx1Yjk3OFx1YjJlNC4gXHVkNjQwXHVjMjE4XHViOTdjIFx1YWMwMFx1YzdhNSBcdWI5Y2VcdWM3NzQgXHVhY2UwXHViOTc4IFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWMyYjlcdWI5YWNcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+XHVjODE1XHVjNzc4XHVjNzc0XHViMjk0IFx1Y2Q1Y1x1YzEyMFx1Yzc0NCBcdWIyZTRcdWQ1NzRcdWMxMWMgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViMjk0IFx1ZDU2ZFx1YzBjMSBcdWM3NzRcdWFlMzBcdWFjNzBcdWIwOTggXHViZTQ0XHVhZTM4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjODA0XHViN2I1XHVjNzQ0IFx1YzEyMFx1ZDBkZFx1ZDU1Y1x1YjJlNC4gXHVjODE1XHVjNzc4XHVjNzc0XHViMjk0IFx1YzEyMFx1YzYwMVx1Yzc3NFx1YWMwMCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjNWJjXHViOWM4XHViMDk4IFx1Yzc5OCBcdWQ1NThcdWIyOTRcdWM5YzAgXHViYWE4XHViOTc4XHViMmU0LiBcdWI2MTAsIFx1YzgxNVx1Yzc3OFx1Yzc3NFx1YjI5NCBcdWMyZTBcdWMwYWNcdWM3NzRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWMxMjBcdWM2MDFcdWM3NzRcdWM1ZDBcdWFjOGMgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWMyMThcdWI5N2MgXHVjNTkxXHViY2Y0XHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxMjBcdWM2MDFcdWM3NzRcdWFjMDAgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1YzJiOVx1YjlhY1x1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVhY2UwXHViOTdjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWMyMThcdWM3NTggXHVjZDFkIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjNmQwIFx1YzcwNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMjE4XHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMTAwKTxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IE5cdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVjMjJiXHVjNzkwXHViMjk0IDEgXHVjNzc0XHVjMGMxIDEwMDAgXHVjNzc0XHVkNTU4XHVjNzc0XHViMmU0LiBcdWI0NTAgXHVjMjE4XHVhYzAwIFx1YWMxOVx1Yzc0MCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YzEyMFx1YzYwMVx1Yzc3NFx1YWMwMCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjMmI5XHViOWFjXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWFjZTBcdWI5N2MgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzIxOFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzAzMiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IklWQU5BIiwiZGVzY3JpcHRpb24iOiI8cD5FdmVuIHRob3VnaCBzaGUgc2F3IFp2b25rbyBzdGVhbCBNaXJrbyYjMzk7cyBtaWNyb3Byb2Nlc3NvciBpbiB0aGUgc2Vjb25kIHRhc2ssIE1pcmtvJiMzOTtzIHNpc3RlciBJdmFuYSBkaWQgbm90IHRlbGwgTWlya28gYmVjYXVzZSBzaGUgbGlrZXMgWnZvbmtvLiBTaGUgc3VnZ2VzdGVkIHRvIGhpbSB0aGF0IHRoZXkgZ28gc2VlIGEgbW92aWUgdG9nZXRoZXIgc28gdGhhdCBzaGUgd291bGQgJnF1b3Q7Zm9yZ2V0JnF1b3Q7IGFib3V0IHRoZSBpbmNpZGVudC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+WnZvbmtvIGRvZXMgbm90IGNhcmUgbXVjaCBmb3IgZ2lybHMgYmVjYXVzZSB0aGV5IHRha2UgYXdheSBwcmVjaW91cyB0aW1lIGhlIHVzdWFsbHkgc3BlbmRzIHByYWN0aWNpbmcgaGlzIG1hdGgtZnUuIEhlIHN1Z2dlc3RlZCB0aGF0IHRoZSB0d28gb2YgdGhlbSBwbGF5IGEgZ2FtZSBhbmQsIGlmIEl2YW5hIHdpbnMsIHRoZXkgd2lsbCBnbyBzZWUgYSBtb3ZpZSB0b2dldGhlci4gSXZhbmEgYWdyZWVkLCBiZWluZyBnb29kIGF0IGp1bXAgcm9wZSBhbmQgc2hlIHNvbWV0aW1lcyBldmVuIGtpY2tzIGEgZm9vdGJhbGwgYXJvdW5kIHdpdGggaGVyIHR3byBicm90aGVycy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+WnZvbmtvIGxhaWQgTiBwb3NpdGl2ZSBpbnRlZ2VycyBpbiBhIGNpcmNsZSBvbiB0aGUgZmxvb3IgYW5kIGV4cGxhaW5lZCB0aGUgcnVsZXM6Jm5ic3A7PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+VGhlIGZpcnN0IHBsYXllciB0YWtlcyBhbnkgbnVtYmVyLiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5UaGUgc2Vjb25kIHBsYXllciB0YWtlcyBlaXRoZXIgb2YgdGhlIHR3byBudW1iZXJzIGFkamFjZW50IHRvIHRoZSBvbmUgdGhlIGZpcnN0IHBsYXllciB0b29rLiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5UaGUgbmV4dCBwbGF5ZXIgdGFrZXMgYSBudW1iZXIgYWRqYWNlbnQgdG8gYW55IG9mIHRoZSBudW1iZXJzIHRha2VuIHNvIGZhciwgYW5kIHNvIG9uIHVudGlsIHRoZXkgcnVuIG91dCBvZiBudW1iZXJzLiBUaGUgcGxheWVyIHRvIHRha2UgbW9yZSBvZGQgbnVtYmVycyAobm90IGRpdmlzaWJsZSBieSAyKSB3aW5zLiZuYnNwOzxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlp2b25rbyBwbGF5cyBvcHRpbWFsbHk7IGhlIGFsd2F5cyBsb29rcyBmb3IgYSBzdHJhdGVneSB0aGF0IGxlYWRzIHRvIGNlcnRhaW4gdmljdG9yeSBvciBhIGRyYXcuIFp2b25rbyBkb2VzIG5vdCBrbm93IGhvdyB3ZWxsIEl2YW5hIHBsYXlzLiBCZWluZyBhIHRydWUgY2F2YWxpZXIsIGhlIGxldCBJdmFuYSBoYXZlIHRoZSBmaXJzdCBtb3ZlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5CdXQgSXZhbmEgb25seSBjYXJlcyBhYm91dCBzaXR0aW5nIG5leHQgdG8gWnZvbmtvIGluIGZyb250IG9mIHRoZSBiaWcgc2NyZWVuIHNvIHNoZSBzZWVrcyBoZWxwIHBsYXlpbmcuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IGZpbmRzIGhvdyBtYW55IGRpZmZlcmVudCBmaXJzdCBtb3ZlcyBJdmFuYSBjYW4gbWFrZSwgc28gdGhhdCBzaGUgaGFzIGEgY2hhbmNlIG9mIHdpbm5pbmcgYWZ0ZXJ3YXJkcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGFuIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAxMDApLCBob3cgbWFueSBudW1iZXJzIHRoZXJlIGFyZSBpbiB0aGUgY2lyY2xlLjxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgTiBpbnRlZ2VycyBzZXBhcmF0ZWQgYnkgc2luZ2xlIHNwYWNlcy4gQWxsIG51bWJlcnMgd2lsbCBiZSBiZXR3ZWVuIDEgYW5kIDEwMDAgKGluY2x1c2l2ZSkuIE5vIHR3byBudW1iZXJzIHdpbGwgYmUgdGhlIHNhbWUuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBkZXNpcmVkIG51bWJlciBvbiBhIHNpbmdsZSBsaW5lLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2006/2007 > Contest #5 5번