Drop the Triples

On a small Caribbean island, the residents love to spend warm summer nights playing card games, and every game they play is themed around triangles. The most popular one is called Triples, and its rules are simple.

Triples is played by two players with a standard deck. Cards are identified only by their value, from 1 (Ace) to 13 (King). The deck is shuffled and placed face down in the middle of the table as a pile called the stock. The two players alternate turns, and the first player takes the first turn. On each turn a player:

• draws the top card of the stock into their hand, and
• optionally drops one or more triples (dropping is not required).

Dropping a triple means choosing three cards from your hand and placing them face up on the table; dropped triples stay there until the end of the game. Only certain sets of three cards form a valid triple, and there are two kinds:

• Perfect triple — three cards whose values are the side lengths of an equilateral triangle, that is, three cards of the same value.
• Common triple — three cards whose values are the side lengths of a valid triangle that is not equilateral.

Three values $a \le b \le c$ form a valid triangle exactly when $a + b > c$. For example, $(5, 5, 5)$ is a perfect triple; $(3, 4, 5)$ and $(3, 9, 9)$ are common triples; $(1, 2, 3)$ is not a triple because $1 + 2 = 3$ (degenerate), and $(1, 2, 5)$ is not a triple because $1 + 2 < 5$.

On a turn a player may drop any number of valid triples (including none). Because each player always knows how many cards remain in the stock, a player may keep every card and drop all triples on their final turn, or drop them along the way; either way, only the final collection of dropped triples affects the result.

The game ends when the stock is empty. The winner is the player who dropped the most perfect triples. If both dropped the same number of perfect triples, the winner is the one who dropped the most common triples. If those are also equal, the game is a tie. Each card a player draws goes only into that player's own hand, so the two players build their triples independently.

Given the stock, determine the winner assuming both players play optimally (each maximizes their own number of perfect triples first, then common triples).

The input contains several test cases. The first line of each test case has one integer $N$, the number of cards in the stock ($6 \le N \le 10^4$). The next line has $N$ integers $X_i$ separated by single spaces, the cards in the stock ($1 \le X_i \le 13$).

The cards are listed in draw order: $X_1$ is drawn first (by the first player), $X_2$ second (by the second player), $X_3$ third (by the first player), and so on, alternating. Values may repeat, and not every value from 1 to 13 needs to appear.

The end of the input is indicated by a line containing $N = 0$, which must not be processed. Input is read from standard input.

For each test case, output a single line containing 1 if the first player to play wins, 2 if the second player wins, or 0 if the game is a tie.

Output is written to standard output.