주 선생과 사탕

시간 제한3초메모리 제한512 MB

요약

사탕 더미 n개가 주어지고, 각 차례에 한 더미에서 양의 개수를 덜어내거나 한 더미를 비어 있지 않은 세 더미로 나눌 수 있을 때 최적 플레이에서 승자를 판정한다.

문제

주 선생이 탁자 위에 사탕 더미 $n$ 개를 놓았다. 두 사람이 다음 게임을 한다. 자기 차례에 각 사람은 한 더미에서 양의 개수만큼 사탕을 가져가거나, 어떤 더미를 비어 있지 않은 세 개의 더 작은 더미로 나눌 수 있다. 마지막 사탕을 가져간 사람이 이긴다.

두 사람이 최적으로 플레이할 때 어느 쪽이 이기는지 구하시오.

첫째 줄에 더미의 개수 $n$ 이 주어진다 ( $1 \le n \le 10^6$ ). 둘째 줄에 각 더미의 사탕 개수 $s_1, \ldots, s_n$ 이 주어진다 ( $1 \le s_i \le 10^9$ ).

첫 번째 사람이 이기면 "First"를, 아니면 "Second"를 출력한다.