시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 70 31 26 43.333%

문제

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

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

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

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

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

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

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

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

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

입력

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

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

출력

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

예제 입력 1

3
3 1 5

예제 출력 1

3
W3sicHJvYmxlbV9pZCI6IjMwMzIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyYjlcdWI5YWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1Yzc1OCBcdWM1ZWNcdWIzZDlcdWMwZGQgXHVjMTIwXHVjNjAxXHVjNzc0XHViMjk0IFx1YzgxNVx1Yzc3OFx1Yzc3NFx1YWMwMCBcdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHViOWM4XHVjNzc0XHVkMDZjXHViODVjXHVkNTA0XHViODVjXHVjMTM4XHVjMTFjXHViOTdjIFx1ZDZkNFx1Y2U1OFx1YjI5NCBcdWFjODNcdWM3NDQgXHViY2Y0XHVjNTU4XHViMmU0LiBcdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNWQwXHVhYzhjIFx1Yzc3NCBcdWMwYWNcdWMyZTRcdWM3NDQgXHViOWQwXHVkNTc0XHVjNTdjIFx1ZDU1OFx1YjI5NFx1YzljMFx1Yjk3YyBcdWFjZTBcdWJiZmNcdWQ1ODhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHVjMTIwXHVjNjAxXHVjNzc0XHViMjk0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YmNmNFx1YjJlNCBcdWM4MTVcdWM3NzhcdWM3NzRcdWI5N2MgXHViMzU0IFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHViOWQwXHVkNTU4XHVjOWMwIFx1YzU0YVx1YzU1OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMTIwXHVjNjAxXHVjNzc0XHViMjk0IFx1YzgxNVx1Yzc3OFx1Yzc3NFx1YzVkMFx1YWM4YyBcdWIzNzBcdWM3NzRcdWQyYjggXHVjMmUwXHVjY2FkXHVjNzQ0IFx1ZDU1OFx1YzYwMFx1YWNlMCwgXHVjNjAxXHVkNjU0XHViOTdjIFx1YWMxOVx1Yzc3NCBcdWJjZjRcdWI3ZWNcdWFjMDRcdWIyZTRcdWJhNzQgXHVjNzc0IFx1YzBhY1x1YzJlNFx1Yzc0NCBcdWFkZjggXHViMjA0XHVhZDZjXHVjNWQwXHVhYzhjXHViM2M0IFx1YjlkMFx1ZDU1OFx1YzljMCBcdWM1NGFcdWFlMzBcdWI4NWMgXHVjNTdkXHVjMThkXHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NGNcdWFjZTBcdWJjZjRcdWIyYzggXHVjODE1XHVjNzc4XHVjNzc0XHViMjk0IFx1YzVlY1x1Yzc5MFx1YzVkMFx1YWM4YyBcdWJjYzQgXHVhZDAwXHVjMmVjXHVjNzc0IFx1YzVjNlx1YzVjOFx1YjJlNC4gXHVhZGY4IFx1Yzc3NFx1YzcyMFx1YjI5NCBcdWM4MTVcdWM3NzhcdWM3NzRcdWFjMDAgXHVjMjE4XHVkNTU5XHViYjM4XHVjODFjXHViOTdjIFx1ZDQ3OFx1YjI5NFx1YjM3MCBcdWJjMjlcdWQ1NzQgXHViNDFjXHViMmU0XHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHVhZGY4XHViMjk0IFx1YzEyMFx1YzYwMVx1Yzc3NFx1YzVkMFx1YWM4YyBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjMmUwXHVjY2FkXHVkNTg4XHVhY2UwLCBcdWM3NzRcdWFlMzBcdWJhNzQgXHVjNjAxXHVkNjU0XHViOTdjIFx1YmNmNFx1YjdlYyBcdWFjMDBcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LiBcdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHVhYzhjXHVjNzg0XHVjNWQwIFx1Yzc5MFx1YzJlMFx1Yzc3NCBcdWM3ODhcdWM1YzhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWM4MTVcdWM3NzhcdWM3NzRcdWM3NTggXHVjODFjXHVjNTQ4XHVjNWQwIFx1YjNkOVx1Yzc1OFx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODE1XHVjNzc4XHVjNzc0XHViMjk0IE5cdWFjMWNcdWM3NTggXHVjNTkxXHVjMjE4XHViOTdjIFx1YzZkMCBcdWM3MDRcdWM1ZDAgXHVjYzI4XHViODQwXHViMzAwXHViODVjIFx1YzRmMFx1YWNlMCBcdWMxMjBcdWM2MDFcdWM3NzRcdWM1ZDBcdWFjOGMgXHVhYzhjXHVjNzg0XHVjNzU4IFx1YWRkY1x1Y2U1OVx1Yzc0NCBcdWMxMjRcdWJhODVcdWQ1ODhcdWI1MzAuPFwvcD5cclxuXHJcbjxwPjEuIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHVhYzAwIFx1YzU0NFx1YmIzNCBcdWMyMmJcdWM3OTBcdWIwOTggXHVkNTU4XHViMDk4IFx1YWNlMFx1Yjk3OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+Mi4gXHViNDUwIFx1YmM4OFx1YzlmOCBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWFjMDAgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWFjMDAgXHVhY2UwXHViOTc4IFx1YzIxOFx1YzVkMCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHViNDUwIFx1YzIxOCBcdWM5MTEgXHVkNTU4XHViMDk4XHViOTdjIFx1YWNlMFx1Yjk3OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+My4gXHVhZGY4IFx1YjJlNFx1Yzc0YyBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWIyOTQgXHVhY2UwXHViOTdjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMjE4XHVhYzAwIFx1YzVjNlx1Yzc0NCBcdWI1NGNcdWFlNGNcdWM5YzAgXHVjOWMwXHVhZTA4XHVhZTRjXHVjOWMwIFx1YWNlMFx1Yjk3OCBcdWMyMThcdWM1ZDAgXHVjNzc4XHVjODExXHVkNTVjIFx1YzIxOCBcdWM5MTFcdWM1ZDBcdWMxMWMgXHVjNTQ0XHViYjM0IFx1YzIyYlx1Yzc5MFx1YjA5OCBcdWFjZTBcdWI5NzhcdWIyZTQuIFx1ZDY0MFx1YzIxOFx1Yjk3YyBcdWFjMDBcdWM3YTUgXHViOWNlXHVjNzc0IFx1YWNlMFx1Yjk3OCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjMmI5XHViOWFjXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4MTVcdWM3NzhcdWM3NzRcdWIyOTQgXHVjZDVjXHVjMTIwXHVjNzQ0IFx1YjJlNFx1ZDU3NFx1YzExYyBcdWFjOGNcdWM3ODRcdWM3NDQgXHVkNTVjXHViMmU0LiBcdWFkZjhcdWIyOTQgXHVkNTZkXHVjMGMxIFx1Yzc3NFx1YWUzMFx1YWM3MFx1YjA5OCBcdWJlNDRcdWFlMzggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM4MDRcdWI3YjVcdWM3NDQgXHVjMTIwXHVkMGRkXHVkNTVjXHViMmU0LiBcdWM4MTVcdWM3NzhcdWM3NzRcdWIyOTQgXHVjMTIwXHVjNjAxXHVjNzc0XHVhYzAwIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWM1YmNcdWI5YzhcdWIwOTggXHVjNzk4IFx1ZDU1OFx1YjI5NFx1YzljMCBcdWJhYThcdWI5NzhcdWIyZTQuIFx1YjYxMCwgXHVjODE1XHVjNzc4XHVjNzc0XHViMjk0IFx1YzJlMFx1YzBhY1x1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YzEyMFx1YzYwMVx1Yzc3NFx1YzVkMFx1YWM4YyBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzIxOFx1Yjk3YyBcdWM1OTFcdWJjZjRcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzEyMFx1YzYwMVx1Yzc3NFx1YWMwMCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjMmI5XHViOWFjXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWFjZTBcdWI5N2MgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzIxOFx1Yzc1OCBcdWNkMWQgXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM2ZDAgXHVjNzA0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMyMThcdWM3NTggXHVhYzFjXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxMDApPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMThcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWMyMmJcdWM3OTBcdWIyOTQgMSBcdWM3NzRcdWMwYzEgMTAwMCBcdWM3NzRcdWQ1NThcdWM3NzRcdWIyZTQuIFx1YjQ1MCBcdWMyMThcdWFjMDAgXHVhYzE5XHVjNzQwIFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjMTIwXHVjNjAxXHVjNzc0XHVhYzAwIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWMyYjlcdWI5YWNcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YWNlMFx1Yjk3YyBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjMjE4XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMDMyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiSVZBTkEiLCJkZXNjcmlwdGlvbiI6IjxwPkV2ZW4gdGhvdWdoIHNoZSBzYXcgWnZvbmtvIHN0ZWFsIE1pcmtvJiMzOTtzIG1pY3JvcHJvY2Vzc29yIGluIHRoZSBzZWNvbmQgdGFzaywgTWlya28mIzM5O3Mgc2lzdGVyIEl2YW5hIGRpZCBub3QgdGVsbCBNaXJrbyBiZWNhdXNlIHNoZSBsaWtlcyBadm9ua28uIFNoZSBzdWdnZXN0ZWQgdG8gaGltIHRoYXQgdGhleSBnbyBzZWUgYSBtb3ZpZSB0b2dldGhlciBzbyB0aGF0IHNoZSB3b3VsZCAmcXVvdDtmb3JnZXQmcXVvdDsgYWJvdXQgdGhlIGluY2lkZW50LiZuYnNwOzxcL3A+XHJcblxyXG48cD5adm9ua28gZG9lcyBub3QgY2FyZSBtdWNoIGZvciBnaXJscyBiZWNhdXNlIHRoZXkgdGFrZSBhd2F5IHByZWNpb3VzIHRpbWUgaGUgdXN1YWxseSBzcGVuZHMgcHJhY3RpY2luZyBoaXMgbWF0aC1mdS4gSGUgc3VnZ2VzdGVkIHRoYXQgdGhlIHR3byBvZiB0aGVtIHBsYXkgYSBnYW1lIGFuZCwgaWYgSXZhbmEgd2lucywgdGhleSB3aWxsIGdvIHNlZSBhIG1vdmllIHRvZ2V0aGVyLiBJdmFuYSBhZ3JlZWQsIGJlaW5nIGdvb2QgYXQganVtcCByb3BlIGFuZCBzaGUgc29tZXRpbWVzIGV2ZW4ga2lja3MgYSBmb290YmFsbCBhcm91bmQgd2l0aCBoZXIgdHdvIGJyb3RoZXJzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5adm9ua28gbGFpZCBOIHBvc2l0aXZlIGludGVnZXJzIGluIGEgY2lyY2xlIG9uIHRoZSBmbG9vciBhbmQgZXhwbGFpbmVkIHRoZSBydWxlczombmJzcDs8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5UaGUgZmlyc3QgcGxheWVyIHRha2VzIGFueSBudW1iZXIuJm5ic3A7PFwvbGk+XHJcblx0PGxpPlRoZSBzZWNvbmQgcGxheWVyIHRha2VzIGVpdGhlciBvZiB0aGUgdHdvIG51bWJlcnMgYWRqYWNlbnQgdG8gdGhlIG9uZSB0aGUgZmlyc3QgcGxheWVyIHRvb2suJm5ic3A7PFwvbGk+XHJcblx0PGxpPlRoZSBuZXh0IHBsYXllciB0YWtlcyBhIG51bWJlciBhZGphY2VudCB0byBhbnkgb2YgdGhlIG51bWJlcnMgdGFrZW4gc28gZmFyLCBhbmQgc28gb24gdW50aWwgdGhleSBydW4gb3V0IG9mIG51bWJlcnMuIFRoZSBwbGF5ZXIgdG8gdGFrZSBtb3JlIG9kZCBudW1iZXJzIChub3QgZGl2aXNpYmxlIGJ5IDIpIHdpbnMuJm5ic3A7PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+WnZvbmtvIHBsYXlzIG9wdGltYWxseTsgaGUgYWx3YXlzIGxvb2tzIGZvciBhIHN0cmF0ZWd5IHRoYXQgbGVhZHMgdG8gY2VydGFpbiB2aWN0b3J5IG9yIGEgZHJhdy4gWnZvbmtvIGRvZXMgbm90IGtub3cgaG93IHdlbGwgSXZhbmEgcGxheXMuIEJlaW5nIGEgdHJ1ZSBjYXZhbGllciwgaGUgbGV0IEl2YW5hIGhhdmUgdGhlIGZpcnN0IG1vdmUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkJ1dCBJdmFuYSBvbmx5IGNhcmVzIGFib3V0IHNpdHRpbmcgbmV4dCB0byBadm9ua28gaW4gZnJvbnQgb2YgdGhlIGJpZyBzY3JlZW4gc28gc2hlIHNlZWtzIGhlbHAgcGxheWluZy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgZmluZHMgaG93IG1hbnkgZGlmZmVyZW50IGZpcnN0IG1vdmVzIEl2YW5hIGNhbiBtYWtlLCBzbyB0aGF0IHNoZSBoYXMgYSBjaGFuY2Ugb2Ygd2lubmluZyBhZnRlcndhcmRzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYW4gaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDEwMCksIGhvdyBtYW55IG51bWJlcnMgdGhlcmUgYXJlIGluIHRoZSBjaXJjbGUuPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBjb250YWlucyBOIGludGVnZXJzIHNlcGFyYXRlZCBieSBzaW5nbGUgc3BhY2VzLiBBbGwgbnVtYmVycyB3aWxsIGJlIGJldHdlZW4gMSBhbmQgMTAwMCAoaW5jbHVzaXZlKS4gTm8gdHdvIG51bWJlcnMgd2lsbCBiZSB0aGUgc2FtZS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIGRlc2lyZWQgbnVtYmVyIG9uIGEgc2luZ2xlIGxpbmUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==