Informatica Online Judge

  저녁 식사 줄서기 [0248 / 00F8]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 116   Total Tried : 171


The Champion of this Problem (C++) : qwazpia - 0ms / 124byte
My Best Submission (C++) : N/A

[]

Background

경곽에서는 저녁식사를 할 때 $1$과 $2$의 번호표를 가지는 $2$개의 그룹을 구성하여 그룹순으로 식사를 한다.

각 학생들은 자신의 그룹 번호 $1$ 또는 $2$ 가 세겨진 멤버십카드를 지참하고 있다.

기본적으로 그룹 $1$ 인 학생들이 앞에, 그룹 $2$ 인 학생들이 뒤에 줄을 서야하는데 오늘따라 학생들이 번호대로 줄을 서지 않아서 저녁식사를 제대로 할 수 없게 되었다.

학생들이 제대로 식사를 하려면 다시 줄을 서야했다.

하지만 매우 머리가 좋은 melongist는 학생들을 다시 줄세우지 않으면서 식사를 할 수 있는 방법을 생각했다.

그 방법은 학생들이 가진 멤버쉽 카드의 번호를 고치는 것이다.

melongist는 그룹 번호가 $2$번인 학생을 $1$로, 또는 그 반대로 고칠 수 있다.

고치다 보면 모든 학생들이 한 그룹에 속하게 되는 경우도 가능하다.


예를들어 $1$, $1$, $1$, $1$, ... 또는 $2$, $2$, $2$, $2$, ...

학생들이 저녁식사를 정상적으로 하기위해(그룹별 줄을 맞추기 위해) melongist가 고쳐야 하는 멤버쉽카드의 수를 최소화 하고 싶다.

여러분이 그 해법을 작성해야 한다.

Input

첫 째줄에 학생의의 수를 나타내는 정수 $n$이 입력된다.
둘 째줄 부터 $n+$1번째 줄까지 각 학생들의 그룹번호 $1$또는 $2$가 주어진다.

[입력값의 정의역]

$1 <= n <= 30,000$

Output

줄을 정상화하기위하여 고쳐야하는 최소의 카드 수를 출력한다.

IO Example

입력
7
2
1
1
1
2
2
1

출력
2


출처 : USACO (http://ace.delos.com)

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]