세 명이 돌 더미에서 번갈아 돌을 가져가며 벤과 크리스가 짜고 안소니를 지게 만들려 할 때, 안소니가 패배를 피할 수 있는지 판정한다.
어려움8게임 이론그리디수학조합론아직 제출이 없습니다시간 제한2초메모리 제한64 MB
문제 설명
예제2
문제
앤서니는 친구 벤, 크리스와 돌 가져가기 게임을 한다. 돌 무더기가 N개 있고 i번째 무더기에는 돌이 Ai개 놓여 있다. 자기 차례가 된 사람은 무더기 하나를 고른 뒤 그 무더기에서 돌을 1개 이상 원하는 만큼 가져갈 수 있다. 차례는 앤서니, 벤, 크리스 순서로 돌아가고 이 순서를 계속 반복한다. 자기 차례에 남은 돌이 하나도 없어 아무것도 가져가지 못하는 사람이 진다.
벤과 크리스는 미리 짜고 앤서니를 지게 만들기로 했다. 둘은 자기가 지는지는 신경 쓰지 않고 앤서니를 패배시키는 것만 노린다. 앤서니는 지지 않으려 한다. 세 사람이 모두 최선을 다해 둘 때 앤서니가 패배를 피할 수 있는지 판정하라.
입력
첫째 줄에 무더기의 개수 N이 주어진다. (1≤N≤105)
둘째 줄에 정수 A1,A2,…,AN이 공백으로 구분되어 주어진다. (1≤Ai≤109)