Sanghun possède $N$ dés cubiques, appelés dans l’ordre dé $1$, dé $2$, $\ldots$, dé $N$.

Chaque face de chaque dé porte un entier entre $1$ et $6$. Les faces distinctes d’un même dé portent toujours des nombres distincts, et les nombres de deux faces opposées ont toujours pour somme $7$.

Sanghun souhaite construire des tours avec ces $N$ dés. La procédure exacte est la suivante.

1. Lancer les $N$ dés sur le sol.

2. Noter le nombre sur la face supérieure de chaque dé. Du dé $1$ au dé $N$, appeler ces nombres $A_1,A_2,\ldots,A_N$.

3. Choisir au moins un dé au sol et construire une nouvelle tour sur un bureau. Les dés peuvent être soulevés et déplacés, mais leur orientation ne doit pas changer. Les dés choisis peuvent être empilés dans n’importe quel ordre, tous verticalement en une seule colonne. Les nombres sur deux faces en contact doivent être égaux.

4. Répéter l’étape 3 jusqu’à ce qu’il ne reste aucun dé au sol.

Par exemple, la procédure peut se dérouler ainsi.

1. Sanghun lance quatre dés au sol. Les faces supérieures des dés $1$ à $4$ montrent respectivement $3,3,5,4$.

2. Sanghun choisit les dés $1$, $2$ et $4$, puis les empile de bas en haut dans l’ordre $1$, $4$, $2$. La face supérieure du dé $1$ et la face inférieure du dé $4$ portent toutes deux $3$ et sont en contact. De même, la face supérieure du dé $4$ et la face inférieure du dé $2$ portent toutes deux $4$ et sont en contact.

3. Sanghun choisit le dé $3$ restant au sol et construit une tour constituée de ce seul dé.

4. Il ne reste aucun dé au sol, donc la procédure se termine. Sanghun a construit deux tours au total.

Sanghun veut choisir l’empilement de façon à minimiser le nombre de tours. Étant donnés les nombres des faces supérieures des $N$ dés après leur lancer, trouvez le nombre minimal de tours possible.

Contraintes

• Tous les nombres donnés sont entiers.

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

• $1\le A_i\le6$ pour tout entier $i$ tel que $1\le i\le N$.

Sous-tâches

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

2. (28 points) Chaque face supérieure porte $3$ ou $4$. Autrement dit, $A_i=3$ ou $A_i=4$ pour tout entier $i$ tel que $1\le i\le N$.

3. (31 points) Pour tous entiers distincts $x,y$ tels que $1\le x,y\le6$, le nombre de dés portant $x$ sur le dessus diffère du nombre de dés portant $y$ sur le dessus.

4. (33 points) Aucune contrainte supplémentaire.

Entrée

La première ligne contient l’entier $N$.

La ligne suivante contient les $N$ entiers $A_1,A_2,\ldots,A_N$ dans l’ordre, séparés par des espaces.

Sortie

Sur la première ligne, affichez le nombre minimal de tours que Sanghun peut construire en choisissant convenablement l’empilement.

Exemples

Entrée 1

4
3 3 5 4

Sortie 1

2

Entrée 2

2
3 4

Sortie 2

1

Entrée 3

5
1 1 6 1 1

Sortie 3

3