시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 177 43 29 27.619%

문제

머리가 나쁜 kcm1700은 머리가 좋은 ntopia를 상대로 한 가지 게임을 하고 있었다. 이 게임은 n개의 자연수로 이루어진 수열을 놓고 진행된다. 이 수는 모두 231 미만이고, 2의 배수가 아닌 수의 총 개수는 홀수이다. 게임의 규칙은 다음과 같다.

  • 수열의 앞 또는 뒤에서 먼저 kcm1700이 한 수 또는 인접한 두 수를 선택한다.
  • 선택한 수들을 제거한다.
  • 그리고 ntopia가 수열의 앞 또는 뒤에서 한 수 또는 인접한 두 수를 선택한다.
  • 선택한 수들을 제거한다.
  • 수를 더 고를 수 없을 때까지 이 과정을 계속 반복한다.
  • 총 합이 짝수(0도 짝수이다)인 사람이 승리한다.

예를 들어 수열이 1 3 5 2 4 6 으로 주어졌다면, kcm1700이 맨 처음에 선택할 수 있는 경우는 (1), (1 3), (6), (4 6) 뿐이다.

ntopia는 무조건 최상의 플레이를 구사하는 천재 플레이어이기 때문에, kcm1700은 주어진 수열에서 ntopia가 실수를 하지 않았을 때 kcm1700이 이길 가능성이 있는지를 게임을 시작하기 전에 미리 알아보고 싶다. kcm1700이 이길 가능성이 있는지 출력하여라.

입력

첫째 줄에 양의 정수 N(1 ≤ N ≤ 3,000)이 하나 주어진다. 둘 째 줄에 자연수 N개가 차례대로 공백을 사이에 두고 주어진다.

출력

첫째 줄에 이길 가능성이 존재한다면 Yes, 그렇지 않다면 No를 출력한다.

예제 입력 1

5
1 5 4 2 7

예제 출력 1

Yes

예제 입력 2

3
2 1 4

예제 출력 2

No

출처

Contest > koi4u > koi4u 2008년 5월 모의고사 B번