Privileged Cows

Interview

Time limit1sMemory limit128 MB

Summary

Given a sequence of 1s, 2s, and 3s, find the minimum number of arbitrary swaps needed to group all 1s first, then all 2s, then all 3s.

Level: Medium5 of 10
Topics: Greedy, Array, Sorting, Implementation
Solved: No attempts yet

Problem

There are $N$ cows ( $1 \le N \le 1000$ ). Based on its milk output, each cow is assigned a privilege number of $1$ , $2$ , or $3$ that determines when it gets to drink at the well: a cow with privilege number $1$ drinks earliest and one with privilege number $3$ drinks latest.

The cows are lined up in some order and must re-arrange themselves so that all the $1$ 's are together at the front of the line, the $2$ 's follow, and the $3$ 's are together at the end.

A single exchange swaps the positions of two cows in the line. Find the minimum number of exchanges needed to order the cows properly.

Input

Line $1$ : a single integer $N$ .
Lines $2 \ldots N+1$ : line $i+1$ contains a single integer, the privilege number of the cow at position $i$ in the line.

Output

Line $1$ : a single integer, the minimum number of exchanges required to order the cows properly.

Hint

Here is one way to sort them (a < marks a position taking part in the exchange):

2   2   2< 1   1
2< 1   1   1   1
1< 2   2   2   2
3   3< 2   2   2 
3   3   3   3< 2
3   3   3   3   3
2   2< 3   3   3
3   3   3   3   3
1   1   1< 2< 3

Examples4

Example 1
Input
```
9
2
2
1
3
3
3
2
3
1
```
Expected output
```
4
```
Example 2
Input
```
6
1
1
2
2
3
3
```
Expected output
```
0
```
Example 3
Input
```
1
3
```
Expected output
```
0
```
Example 4
Input
```
4
2
2
2
2
```
Expected output
```
0
```