Les vaches sont très difficiles sur leurs voisines de dîner. Elles forment deux groupes $1$ et $2$, exigeant de dîner ensemble dans l’ordre, $1$ au début de la file, $2$ à la fin. Le problème apparaît en faisant la queue à la grange pour entrer dans la zone d’alimentation.

Chaque vache $i$ porte une carte gravée $D_{i}$ ($1 \le D_{i} \le 2$), son groupe. Les $N$ vaches ($1 \le N \le 30{,}000$) sont alignées mais pas selon les groupes des cartes.

Le travail de FJ est facile : parcourir la file, rayer l’ancien numéro et en écrire un nouveau pour changer le groupe. Il crée ainsi des groupes tels que 112222 ou 111122, triés par numéro croissant. Parfois il ne reste qu’un groupe, comme 1111 ou 222.

FJ est aussi paresseux que les autres. Quel est le minimum absolu de cartes à modifier pour grouper correctement les partenaires ? Il doit uniquement changer les numéros, sans réordonner les vaches.

Entrée

Lisez l’entrée standard.

• Ligne 1 : entier $N$.
• Lignes $2,\ldots,N+1$ : la ligne $i+1$ décrit le groupe préféré de la vache $i$ par l’entier $D_{i}$.

Sortie

Écrivez sur la sortie standard.

• Ligne 1 : entier, nombre minimal de cartes que Farmer John doit modifier pour le regroupement décrit.

Exemples

Entrée 1

7
2
1
1
1
2
2
1

Sortie 1

2

Remarque

Sept vaches ; toutes sauf trois préfèrent actuellement le groupe $1$.

Changez les cartes de la première et de la dernière vache.

Crédits du problème : Ionescu Victor et Brian Dean, 2007