P2837 [USACO08FEB] Dining Cows B

To avoid overcrowding in the dining hall, FJ requires the cows to eat in $2$ batches. Every day before dinner, the cows line up in front of the dining hall to enter. According to FJ’s plan, all cows in batch $2$ stand at the end of the line, while the front part of the line is occupied by cows designated as batch $1$. Since the cows do not understand FJ’s arrangement, lining up before dinner has become a big hassle. Cow $i$ holds a card that indicates her dining batch $D_i$. Although all $N$ cows stand in a neat line, it is obvious that the numbers on the cards are completely jumbled. After several chaotic re-lineups, FJ finds a simpler method: without moving the cows, he walks from the head to the tail of the line and changes the number on the card of any cow he believes is in the wrong batch, eventually obtaining a line in which all cows of each group stand together, for example, $112222$ or $111122$. Sometimes, FJ will even make the entire line consist of only $1$ group (for example, $1111$ or $222$). You also know that FJ is lazy. He wants to know the minimum number of cows’ card numbers he must change to achieve his goal. None of the cows moves while FJ is changing the card numbers.

The first line contains an integer $N$ ($1 \le N \le 3 \times 10 ^ 4$). Lines $2$ to $N + 1$ each contain $1$ integer, the dining batch $D_i$ of the $i$-th cow ($1 \le D_i \le 2$).

Output $1$ integer, the minimum number of cows’ card numbers FJ must change to make the sequence match his plan.

Constraints: $1 \le N \le 3 \times 10 ^ 4$. Translated by ChatGPT 5