군대 훈련

시간 제한2초메모리 제한1024 MB

요약

병사 n명의 준비도 점수(1부터 3까지)가 주어질 때, 전체의 절반 이상이 완전 준비 상태(1)가 되도록 필요한 최소 인원을 구합니다.

난이도: 쉬움10점 중 1점
유형: 배열, 구현
정답자: 아직 제출이 없습니다

문제

출진 전에는 승리를 확신해야 하므로, 모든 병사가 어떤 상황에도 대비되어 있어야 한다. 오늘 아침 점검에서 키틀니스와 피타는 부대의 전투력을 평가했다. 병사마다 1부터 3까지의 수를 종이에 적어 그 병사의 준비 상태로 삼았다. 1은 전투 준비가 완전히 끝난 상태이고, 3은 아무것도 할 줄 모르는 상태다. 키틀니스는 병사의 절반 이상이 전투 준비 완료 상태이면 반드시 이기는 전술을 생각해냈다. 종이를 보면서 그녀는 묻는다. 이 전술로 승리를 보장하려면 추가로 완전히 훈련시켜야 할 병사의 최소 인원은 몇 명인가. 그녀에게는 생각할 시간이 없으니, 그 수를 구하는 일을 도와 달라.

입력

첫 번째 줄에 병사의 수 $n$ ( $1 \le n \le 100\,000$ )이 주어진다. 두 번째 줄에는 종이에 적힌 $n$ 개의 정수 $a_i$ ( $1 \le a_i \le 3$ )가 주어진다.

출력

부대의 절반 이상이 전투 준비 완료 상태가 되어 승리가 보장되도록, 완전히 준비시켜야 할 병사의 최소 인원을 출력한다.

예제2

예제 1
입력
```
3
1 2 3
```
예상 출력
```
1
```
예제 2
입력
```
3
1 1 2
```
예상 출력
```
0
```