Eating Together

The cows are very particular about their dinner companions. They have split into three dining groups (numbered 1, 2, and 3 for convenience), and each group insists on eating together. When all $N$ cows ($1 \le N \le 30\,000$) line up for feeding, however, they are not arranged by dining group.

Each cow $i$ carries a card engraved with a number $D_i$ ($1 \le D_i \le 3$) indicating her dining group.

Farmer John walks down the line and may change a cow's group by erasing the old number on her card and writing a new one. His goal is to make the group numbers, read along the line, sorted in either non-decreasing order (for example 111222333) or non-increasing order (for example 333222111). He may only change the numbers on the cards; he may not rearrange the cows in line.

Find the minimum number of cards he must change so that the final sequence of group numbers is sorted in either ascending or descending order.

• Line 1: an integer $N$.
• Lines 2 through $N+1$: line $i+1$ contains a single integer $D_i$, the current dining group of the $i$-th cow.

• A single integer: the minimum number of changes needed so that the final sequence is sorted in either non-decreasing or non-increasing order.