우선권을 가진 소들

$N$마리의 소가 있다 ($1 \le N \le 1000$). 각 소는 우유 생산량에 따라 $1$, $2$, $3$ 중 하나의 우선권 번호를 부여받으며, 이 번호는 우물에서 물을 마시는 순서를 결정한다. 우선권 번호가 $1$인 소가 가장 먼저 마시고, $3$인 소가 가장 나중에 마신다.

소들은 어떤 순서로 한 줄로 서 있으며, 우선권 번호가 $1$인 소들이 모두 줄의 앞쪽에, $2$인 소들이 그 뒤에, $3$인 소들이 맨 뒤에 모이도록 다시 정렬해야 한다.

한 번의 교환은 줄에 있는 두 소의 위치를 서로 바꾸는 것이다. 소들을 올바르게 정렬하는 데 필요한 교환의 최소 횟수를 구하여라.

• 첫째 줄: 정수 $N$
• 둘째 줄부터 $N+1$번째 줄까지: $i+1$번째 줄에는 줄에서 $i$번째 위치에 있는 소의 우선권 번호가 하나씩 주어진다.

• 첫째 줄: 소들을 올바르게 정렬하는 데 필요한 최소 교환 횟수를 나타내는 정수 하나

다음은 정렬하는 한 가지 방법이다 (< 표시는 교환에 참여하는 위치를 나타낸다):

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