공격을 시작하기 전에는 항상 승리를 확신하는 것이 중요하며, 이를 위해서는 모든 병사들이 모든 상황에 잘 준비되어 있어야 합니다. 오늘 아침 점검에서 캣니스와 피트는 그들의 군대의 전투력을 평가했습니다. 그들은 각 병사에 대해 1부터 3까지의 숫자를 종이에 적었습니다 - 이는 그들의 준비 상태를 나타냅니다(1 - 전투 준비 완료, 3 - 아무것도 할 줄 모름).
하지만 사실 승리를 위해서는 항상 전체 군대가 훈련되어 있을 필요는 없습니다. 캣니스는 병사들의 적어도 절반이 전투 준비가 완료되어 있다면 확실히 승리할 수 있는 전술을 고안했습니다. 병사들의 특성이 적힌 종이를 보면서, 지도자는 의문을 가졌습니다: 그녀의 전술로 승리를 보장받기 위해서는 최소 몇 명의 병사를 더 완전히 훈련시켜야 할까요? 그녀에게는 생각할 시간이 전혀 없으니, 이 수를 찾는 것을 도와주세요.
입력
입력 파일의 첫 번째 줄에는 병사의 수를 나타내는 정수 \(n\) (\(1 \le n \le 100\,000\))이 주어집니다.
두 번째 줄에는 종이에 적힌 정보 - \(n\)개의 정수 \(a_i\) (\(1 \le a_i \le 3\))가 있습니다.
출력
출력 파일의 유일한 줄에 무조건적인 승리를 위해 완전히 훈련시켜야 하는 최소 병사 수를 출력하세요.
hanzch 2년 전 5
군대 훈련
문제
공격을 시작하기 전에는 항상 승리를 확신하는 것이 중요하며, 이를 위해서는 모든 병사들이 모든 상황에 잘 준비되어 있어야 합니다. 오늘 아침 점검에서 캣니스와 피트는 그들의 군대의 전투력을 평가했습니다. 그들은 각 병사에 대해 1부터 3까지의 숫자를 종이에 적었습니다 - 이는 그들의 준비 상태를 나타냅니다(1 - 전투 준비 완료, 3 - 아무것도 할 줄 모름).
하지만 사실 승리를 위해서는 항상 전체 군대가 훈련되어 있을 필요는 없습니다. 캣니스는 병사들의 적어도 절반이 전투 준비가 완료되어 있다면 확실히 승리할 수 있는 전술을 고안했습니다. 병사들의 특성이 적힌 종이를 보면서, 지도자는 의문을 가졌습니다: 그녀의 전술로 승리를 보장받기 위해서는 최소 몇 명의 병사를 더 완전히 훈련시켜야 할까요? 그녀에게는 생각할 시간이 전혀 없으니, 이 수를 찾는 것을 도와주세요.
입력
입력 파일의 첫 번째 줄에는 병사의 수를 나타내는 정수 \(n\) (\(1 \le n \le 100\,000\))이 주어집니다.
두 번째 줄에는 종이에 적힌 정보 - \(n\)개의 정수 \(a_i\) (\(1 \le a_i \le 3\))가 있습니다.
출력
출력 파일의 유일한 줄에 무조건적인 승리를 위해 완전히 훈련시켜야 하는 최소 병사 수를 출력하세요.
예제
예제 입력 1
예제 출력 1
예제 입력 2
예제 출력 2