트리플 내려놓기

카리브해의 작은 섬 주민들은 따뜻한 여름밤이면 카드 게임을 즐기는데, 이들이 하는 모든 게임은 삼각형을 주제로 삼는다. 그중 가장 인기 있는 게임이 트리플(Triples) 이며, 규칙은 간단하다.

트리플은 표준 카드 한 벌로 두 사람이 하는 게임이다. 카드는 값으로만 구분하며, 값은 1(에이스)부터 13(킹)까지다. 카드를 잘 섞어 탁자 가운데에 뒷면이 보이도록 쌓아 두는데, 이 더미를 스톡(stock) 이라고 한다. 두 사람은 번갈아 차례를 진행하며, 첫 번째 차례는 1번 참가자가 맡는다. 각 차례에 참가자는 다음을 한다.

• 스톡의 맨 위 카드를 뽑아 자기 손패에 넣는다.
• 원한다면 트리플을 하나 이상 내려놓는다(내려놓지 않아도 된다).

트리플을 내려놓는다는 것은 손패에서 카드 세 장을 골라 탁자에 앞면이 보이도록 놓는 것이다. 한번 내려놓은 트리플은 게임이 끝날 때까지 그대로 둔다. 세 장이 유효한 트리플이 되려면 조건을 만족해야 하며, 트리플에는 두 종류가 있다.

• 퍼펙트 트리플 — 세 카드의 값이 정삼각형의 세 변 길이가 되는 경우, 즉 값이 모두 같은 세 장.
• 커먼 트리플 — 세 카드의 값이 정삼각형이 아닌 유효한 삼각형의 세 변 길이가 되는 경우.

세 값 $a \le b \le c$ 가 유효한 삼각형을 이루는 조건은 $a + b > c$ 이다. 예를 들어 $(5, 5, 5)$ 는 퍼펙트 트리플이고, $(3, 4, 5)$ 와 $(3, 9, 9)$ 는 커먼 트리플이다. 반면 $(1, 2, 3)$ 은 $1 + 2 = 3$ 이라 삼각형이 되지 못하고, $(1, 2, 5)$ 도 $1 + 2 < 5$ 라 삼각형이 아니다.

한 차례에 참가자는 유효한 트리플을 원하는 만큼(0개 포함) 내려놓을 수 있다. 각 참가자는 스톡에 남은 카드 수를 항상 알기 때문에, 카드를 모아 두었다가 마지막 차례에 몰아서 내려놓아도 되고 중간중간 내려놓아도 된다. 어느 쪽이든 최종적으로 내려놓은 트리플의 구성만이 결과를 결정한다.

스톡이 비면 게임이 끝난다. 승자는 퍼펙트 트리플을 더 많이 내려놓은 참가자다. 두 사람이 내려놓은 퍼펙트 트리플 수가 같으면 커먼 트리플을 더 많이 내려놓은 사람이 이긴다. 그것마저 같으면 무승부다. 참가자가 뽑은 카드는 오직 그 참가자의 손패로만 들어가므로, 두 사람은 각자 독립적으로 트리플을 만든다.

스톡이 주어질 때, 두 참가자가 모두 최적으로 플레이한다고 가정하고(각자 퍼펙트 트리플 수를 먼저, 그다음 커먼 트리플 수를 최대화) 승자를 구하여라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 스톡의 카드 수 $N$ 이 주어진다 ($6 \le N \le 10^4$). 다음 줄에는 스톡의 카드를 나타내는 $N$ 개의 정수 $X_i$ 가 공백 하나로 구분되어 주어진다 ($1 \le X_i \le 13$).

카드는 뽑는 순서대로 나열된다. $X_1$ 을 (1번 참가자가) 가장 먼저 뽑고, $X_2$ 를 (2번 참가자가) 두 번째로, $X_3$ 을 세 번째로 뽑는 식으로 번갈아 진행한다. 같은 값이 여러 번 나올 수 있고, 1부터 13까지 모든 값이 반드시 등장하지는 않는다.

입력의 끝은 $N = 0$ 인 줄로 나타내며, 이 줄은 처리하지 않는다. 입력은 표준 입력으로 읽는다.

각 테스트 케이스마다 한 줄을 출력한다. 먼저 플레이하는 1번 참가자가 이기면 1, 2번 참가자가 이기면 2, 무승부이면 0 을 출력한다.

출력은 표준 출력으로 쓴다.