Problem Description

Sanghun has $N$ standard six-faced dice. Call them the $1$st die, the $2$nd die, $\ldots$, the $N$th die, in order.

Each die has an integer from $1$ to $6$ written on each of its six faces. On the same die, any two different faces have different numbers, and the sum of the numbers on any two opposite faces is always $7$.

Sanghun wants to use these $N$ dice to build dice towers. The process is as follows:

1. Throw all $N$ dice onto the ground.
2. Record the number on the top face of each die. In the order from the $1$st die to the $N$th die, denote these top-face numbers by $A_1, A_2, \cdots, A_N$.
3. Choose at least one die from those still on the ground and build a new tower on the table. You may pick up dice from the ground, but you may not change their orientation. You may choose any ordering of the selected dice, and you must stack all of them vertically into a single column. At this time, the numbers written on any two faces that touch must be the same.
4. Repeat step 3 until no dice remain on the ground.

For example, the process can be as follows:

1. Sanghun throws $4$ dice on the ground, and the top-face numbers of the $1$st through $4$th dice are $3, 3, 5, 4$, respectively.
2. Sanghun selects the $1$st, $2$nd, and $4$th dice from the ground, and builds a tower in the order (from bottom to top) of the $1$st, $4$th, and $2$nd dice. The top face of the $1$st die and the bottom face of the $4$th die both have $3$, so these faces can touch. Also, the top face of the $4$th die and the bottom face of the $2$nd die both have $4$, so these faces can touch as well.
3. Sanghun selects the remaining $3$rd die on the ground and builds a tower consisting of only one die.
4. No dice remain on the ground, so the process ends. In total, Sanghun built $2$ towers.

Sanghun wants to decide how to build the towers so that the final number of towers is minimized. Given the numbers on the top faces after throwing the $N$ dice, find the minimum possible number of towers in the end.

Input Format

The first line contains an integer $N$.

The second line contains $N$ integers $A_1, A_2, \cdots, A_N$, separated by spaces.

Output Format

Print the minimum possible number of towers that can be built when Sanghun chooses an optimal way to build them.

4
3 3 5 4

2

2
3 4

1

5
1 1 6 1 1

3

Hint

Constraints

• All given numbers are integers.
• $2 \le N \le 200\,000$
• For each integer $i$ ($1 \le i \le N$), $1 \le A_i \le 6$

Subtasks

1. ($8$ points) $N = 2$.
2. ($28$ points) The number on the top face is $3$ or $4$. That is, for each integer $i$ ($1 \le i \le N$), $A_i = 3$ or $A_i = 4$.
3. ($31$ points) For any two distinct integers $x, y$ ($1 \le x, y \le 6$), the number of dice whose top face is $x$ is different from the number of dice whose top face is $y$.
4. ($33$ points) No additional constraints.

Translated by ChatGPT-5.6.

Translated by ChatGPT 5