23758번 - 중앙값 제거

문제

$N$개의 자연수 $a_1,ドル $a_2,ドル $...,ドル $a_N$이 주어진다. 0을 좋아하는 amel은 $N$개의 수 중 0이 등장할 때까지 다음 연산을 반복하려고 한다.

• 중앙값을 2로 나누고 나머지는 버린다.

중앙값은 $N$개의 수를 오름차순으로 나열했을 때 $\lfloor\cfrac{N+1}{2}\rfloor$번째에 위치한 수이다. 또한 $\lfloor x\rfloor$은 $x$ 이하이면서 가장 큰 정수를 뜻한다.

예를 들어, $[7, 3, 9, 5]$ 에서 한 번의 연산을 수행하면 $[7, 3, 9, 2]$가 된다.

amel이 몇 번의 연산을 수행하여야 목표를 달성할 수 있을지 계산해주자.

입력

첫째 줄에 수의 개수 $N$이 주어진다. (1ドル \le N \le 2 \times 10^6$)

둘째 줄에 자연수 $a_1,ドル $a_2,ドル $...,ドル $a_N$이 공백을 사이에 두고 주어진다. (1ドル \le a_i \le 10^9$)

입력되는 수가 매우 많음에 유의하자.

출력

amel이 수행하여야 하는 연산의 횟수를 한 줄로 출력한다.

제한

힌트

C, C++에서 std::cin을 사용하면 시간 초과를 받을 수 있습니다. scanf를 사용하거나, 이 링크 또는 검색을 통해 빠른 입력방법을 사용하는 것을 추천드립니다.