32864번 - 지나칠 수 없는 지하철 게임

문제

세훈이와 민아는 지하철 노선도와 지하철 모형을 이용해 게임을 하려 한다.

지하철 노선도에는 하나의 노선만 그려져 있으며, 해당 노선은 $N$개의 역이 일렬로 이어진 형태이다. 구체적으로, 각 역에는 1ドル$부터 $N$까지의 번호가 차례대로 매겨져 있으며, 1ドル\le i<N$인 모든 정수 $i$에 대해 $i$번 역의 다음 역은 $i+1$번 역이다. 즉, 1ドル$번 역의 다음 역은 2ドル$번 역, 2ドル$번 역의 다음 역은 3ドル$번 역, $\cdots,ドル $N-1$번 역의 다음 역은 $N$번 역이다.

1ドル$번 역과 $N$번 역을 제외한 각 역은 환승역이거나 일반 역이며, 출발역인 1ドル$번 역과 종착역인 $N$번 역은 항상 일반 역이다.

세훈이와 민아가 진행할 게임의 규칙은 다음과 같다.

1. 지하철 모형을 1ドル$번 역에 놓는다.
2. 세훈이가 먼저 시작하며, 이후 번갈아 가며 턴을 진행한다.
3. 각 턴마다 지하철 모형을 다음 역으로 옮기는 행동을 한 번 이상, 원하는 만큼 반복한 뒤 턴을 넘긴다. 단, 모형이 움직인 이후 환승역에 도착했다면 더 이상 움직일 수 없다. 즉, 환승역에 도착하는 즉시 상대에게 턴이 넘어간다.
4. 자신의 턴에 지하철 모형을 $N$번 역에 놓는 사람이 승리한다.

세훈이와 민아는 항상 승리하기 위해 최선의 선택을 한다. 지하철 노선의 정보가 주어질 때 승자를 구하는 프로그램을 작성해 보자.

입력

첫째 줄에 역의 수 $N$이 주어진다. $(2\leq N\leq 500,円 000)$

둘째 줄에 각 역의 정보를 나타내는 $N$개의 정수 $A_1,ドル $\cdots,ドル $A_N$이 공백으로 구분되어 주어진다. $i$번 역이 일반 역이라면 $A_i=0$이며, 환승역이라면 $A_i=1$이다. $A_1$과 $A_N$은 항상 0ドル$이다.

출력

첫째 줄에 세훈이가 이기면 mnx, 민아가 이기면 alsdkffhgk를 출력한다.

제한

힌트