Sanghun has $N$ cubic dice, called die $1$, die $2$, $\ldots$, die $N$ in order.

Each face of every die bears an integer from $1$ to $6$. Different faces of the same die always bear different numbers, and the numbers on opposite faces always sum to $7$.

Sanghun wants to build dice towers using the $N$ dice. The exact procedure is as follows.

1. Roll all $N$ dice on the floor.

2. Record the number on the top face of each die. In order from die $1$ to die $N$, call these numbers $A_1,A_2,\ldots,A_N$.

3. Select at least one die from the floor and build one new tower on a desk. The dice may be lifted from the floor and moved, but their orientations must not change. The selected dice may be stacked in any order, and all must be stacked vertically in a single column. The numbers on any two touching faces must be equal.

4. Repeat step 3 until no dice remain on the floor.

For example, the process may proceed as follows.

1. Sanghun rolls four dice on the floor. The top faces of dice $1$ through $4$ show $3,3,5,4$, respectively.

2. Sanghun selects dice $1$, $2$, and $4$ from the floor, and stacks them in the order die $1$, die $4$, die $2$ from bottom to top. The top of die $1$ and bottom of die $4$ both show $3$ and touch each other. Also, the top of die $4$ and bottom of die $2$ both show $4$ and touch each other.

3. Sanghun selects die $3$, which remains on the floor, and builds a tower consisting of that one die.

4. No dice remain on the floor, so the process ends. Sanghun has built two towers in total.

Sanghun wants to choose how to stack the dice to minimize the number of towers. Given the top-face number of each die after rolling the $N$ dice, find the minimum possible number of towers.

Constraints

• All given numbers are integers.

• $2\le N\le200\,000$.

• $1\le A_i\le6$ for every integer $i$ with $1\le i\le N$.

Subtasks

1. (8 points) $N=2$.

2. (28 points) Every top-face number is $3$ or $4$. That is, $A_i=3$ or $A_i=4$ for every integer $i$ with $1\le i\le N$.

3. (31 points) For any two distinct integers $x,y$ with $1\le x,y\le6$, the number of dice with $x$ on top differs from the number with $y$ on top.

4. (33 points) No additional constraints.

Input

The first line contains the integer $N$.

The next line contains the $N$ integers $A_1,A_2,\ldots,A_N$ in order, separated by spaces.

Output

On the first line, print the minimum number of towers Sanghun can build by choosing the stacking method appropriately.

Examples

Input 1

4
3 3 5 4

Output 1

2

Input 2

2
3 4

Output 2

1

Input 3

5
1 1 6 1 1

Output 3

3