문제

우진이는 오늘 아침 $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$의 최솟값을 구해보자.

예제 입력 1

4
4 2 2 1

예제 출력 1

3

$X=3$일 때, 민석이가 모든 식물이 영원히 시들지 않도록 물을 주는 방법 중 하나는 다음과 같다.

민석이가 처음으로 식물에 물을 주는 날을 $1$번째 날이라고 할 때, 임의의 양의 정수 $k$에 대해서 다음과 같이 물을 준다.

• $2k-1$번째 날에는 $1,2,4$번째 식물에 물을 준다.
• $2k$번째 날에는 $2,3,4$번째 식물에 물을 준다.

이 방법 외에도 모든 식물이 영원히 시들지 않도록 하는 방법은 여러 가지가 있지만, $X$가 $3$보다 작을 때 모든 식물이 영원히 시들지 않도록 하는 방법은 없다.

예제 입력 2

2
1 1

예제 출력 2

2

예제 입력 1

5
4 16 2 32 8

예제 출력 1

1

노트

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