hanzch   2년 전


군대 훈련

시간 제한 메모리 제한



2초 1024 MB



문제

공격을 시작하기 전에는 항상 승리를 확신하는 것이 중요하며, 이를 위해서는 모든 병사들이 모든 상황에 잘 준비되어 있어야 합니다. 오늘 아침 점검에서 캣니스와 피트는 그들의 군대의 전투력을 평가했습니다. 그들은 각 병사에 대해 1부터 3까지의 숫자를 종이에 적었습니다 - 이는 그들의 준비 상태를 나타냅니다(1 - 전투 준비 완료, 3 - 아무것도 할 줄 모름).

하지만 사실 승리를 위해서는 항상 전체 군대가 훈련되어 있을 필요는 없습니다. 캣니스는 병사들의 적어도 절반이 전투 준비가 완료되어 있다면 확실히 승리할 수 있는 전술을 고안했습니다. 병사들의 특성이 적힌 종이를 보면서, 지도자는 의문을 가졌습니다: 그녀의 전술로 승리를 보장받기 위해서는 최소 몇 명의 병사를 더 완전히 훈련시켜야 할까요? 그녀에게는 생각할 시간이 전혀 없으니, 이 수를 찾는 것을 도와주세요.

입력

입력 파일의 첫 번째 줄에는 병사의 수를 나타내는 정수 \(n\) (\(1 \le n \le 100\,000\))이 주어집니다.

두 번째 줄에는 종이에 적힌 정보 - \(n\)개의 정수 \(a_i\) (\(1 \le a_i \le 3\))가 있습니다.

출력

출력 파일의 유일한 줄에 무조건적인 승리를 위해 완전히 훈련시켜야 하는 최소 병사 수를 출력하세요.

예제

예제 입력 1

3 1 2 3

예제 출력 1

1

예제 입력 2

3 1 1 2

예제 출력 2

0

댓글을 작성하려면 로그인해야 합니다.