식물 기르기

우진이는 오늘 아침 $N$개의 식물을 밭에 심었다. $i$번째 식물은 $a_i$일 연속으로 물을 받지 못하면 시들어버리는데, 특이하게도 $a_i$는 $2$의 거듭제곱이다.

우진이는 오늘 아침 모든 식물에 물을 주었다. 우진이는 민석이에게 내일부터 매일 아침 $N$개의 식물 중에서 $X$개의 식물에만 물을 주라고 시켰다. 민석이는 모든 식물이 영원히 시들지 않도록 최선을 다해서 $X$개의 식물을 골라 물을 준다.

$X$의 값에 따라 모든 식물이 영원히 시들지 않도록 하는 것이 불가능할 수도 있다. 우진이는 적절한 $X$를 정해서 민석이에게 알려주려고 한다. 민석이가 모든 식물이 영원히 시들지 않도록 할 수 있는 $X$의 최솟값을 구해보자.

첫째 줄에 정수 $N(1\le N\le 100\, 000)$이 주어진다.

둘째 줄에 정수 $a_1,a_2,\cdots ,a_N(1\le a_i\le 2^{16};$ $a_i$는 $2$의 거듭제곱$)$이 공백으로 구분되어 주어진다.

민석이가 최선을 다한다면 모든 식물이 영원히 시들지 않도록 할 수 있는 $X$의 최솟값을 구해보자.

본문의 이미지는 출제자가 직접 그린 동방 프로젝트 2차 창작물입니다.