Dining Cows

Interview

Time limit1sMemory limit128 MB

Summary

Given a sequence of 1s and 2s, find the minimum number of values to change so the sequence becomes nondecreasing.

Level: Medium4 of 10
Topics: Dynamic programming, Prefix sum, Greedy, Array
Solved: No attempts yet

Problem

The cows are very picky about their dinner partners. They have split into two groups (numbered 1 and 2) that insist on dining in order: group 1 at the front of the line and group 2 at the back. Trouble starts when they line up at the barn to enter the feeding area.

Each cow $i$ carries a card engraved with $D_i$ ( $1 \le D_i \le 2$ ) indicating her dining group. All $N$ ( $1 \le N \le 30{,}000$ ) cows have lined up, but it is easy to see that they are not grouped by their cards.

Farmer John walks down the line and changes a cow's group assignment by crossing out the old number and writing in a new one. His goal is to make the cards sorted in ascending order, such as 112222 or 111122. Occasionally he might end up with only one group left (for example 1111 or 222).

Farmer John is lazy but curious: what is the minimum number of cards he must change to create a proper grouping of dining partners? He may only change card numbers; he must not rearrange the cows standing in line.

Input

Line 1: A single integer $N$ .
Lines 2 to $N+1$ : Line $i+1$ contains a single integer $D_i$ , cow $i$ 's dining group.

Output

A single integer: the minimum number of cards Farmer John must change so that the cows are sorted into eating groups as described.

Examples2

Example 1
Input
```
7
2
1
1
1
2
2
1
```
Expected output
```
2
```
Example 2
Input
```
6
1
1
2
2
2
2
```
Expected output
```
0
```