레이팅 미적용두 번째 문제에서 Zvonko가 Mirko의 마이크로프로세서를 훔치는 것을 보았지만, Mirko의 여동생 Ivana는 Zvonko를 좋아하기 때문에 Mirko에게 말하지 않았다. 그녀는 그 일을 "잊어 주는" 대가로 함께 영화를 보러 가자고 Zvonko에게 제안했다.
Zvonko는 여자아이들에게 별로 관심이 없다. 평소 수학 수련에 쓰는 소중한 시간을 빼앗기기 때문이다. 그는 둘이 게임을 해서 Ivana가 이기면 함께 영화를 보러 가자고 제안했다. Ivana는 동의했다. 그녀는 줄넘기를 잘하고 가끔은 두 오빠와 축구공을 차기도 하니까.
Zvonko는 바닥에 양의 정수 \(N\)개를 원형으로 늘어놓고 규칙을 설명했다:
- 첫 번째 플레이어는 아무 수나 가져간다.
- 두 번째 플레이어는 첫 번째 플레이어가 가져간 수와 인접한 두 수 중 하나를 가져간다.
- 다음 플레이어는 지금까지 가져간 수들 중 어느 하나와 인접한 수를 가져가고, 수가 다 없어질 때까지 이렇게 계속한다. 홀수(\(2\)로 나누어떨어지지 않는 수)를 더 많이 가져간 플레이어가 이긴다.
Zvonko는 최적으로 플레이한다. 그는 항상 확실한 승리 또는 무승부로 이어지는 전략을 찾는다. Zvonko는 Ivana가 얼마나 잘하는지는 모른다. 진정한 신사답게 그는 Ivana에게 첫 수를 양보했다.
하지만 Ivana는 큰 화면 앞에서 Zvonko 옆에 앉는 것에만 관심이 있어서, 게임에 도움을 구하고 있다.
Ivana가 이후에 이길 가능성이 남는 서로 다른 첫 수가 몇 가지인지 찾는 프로그램을 작성하시오.
입력의 첫째 줄에 원에 놓인 수의 개수인 정수 \(N\) (\(1 \le N \le 1000\))이 주어진다.
둘째 줄에 공백 하나로 구분된 정수 \(N\)개가 주어진다. 모든 수는 \(1\) 이상 \(10^9\) 이하이다. 같은 수는 두 번 나오지 않는다.
구하는 수를 한 줄에 출력한다.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 70점 |
3
3 1 53Whichever number Ivana takes first, she'll end up with two odd numbers, and Zvonko will have gotten only one.
4
1 2 3 42If Ivana takes one of the even numbers, Zvonko will take one of the odd numbers and ensure a draw. If she takes an odd number, Zvonko will have to take an even number and then lose because Ivana can take the other odd number.
8
4 10 5 2 9 8 1 75