시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 31 12 11 37.931%

문제

민호는 N개의 박스를 가지고 있다. 어느날 박스가 너무 많아져 박스를 정리하고 싶어졌다. 하지만 평범한 박스정리가 너무 지루하다고 생각한 민호는 재미를 위해 몇가지 규칙을 정하고 박스를 정리하기로 생각했다. 규칙은 아래와 같다.

  1. 박스 x의 크기를 V[x], 박스 y의 크기를 V[y]라 할 때 V[y]는 적어도 V[x]의 두배는 되어야지 x를 y에 넣을 수 있다.
  2. 박스 x를 박스 y에 넣었다면 y는 다른 박스에 넣지 못한다. 한 박스안에 들어있는 모든 박스는 많아야 한 개이다.

위와 같은 규칙을 지켜 박스 정리를 할 때 최적의 경우를 구해보자. 최적의 경우라 하면 눈에 보이는 박스의 개수가 최소가 되는 경우를 의미한다.

입력

첫째 줄에 민호가 가지고 있는 박스의 개수 N (1 ≤ N ≤ 500,000) 이 주어진다.

두번 째 줄부터 N개의 줄에 걸쳐 민호가 가지고 있는 박스들의 크기 V (1 ≤ V ≤ 100,000) 이 주어진다.

출력

규칙을 지켜가며 박스 정리를 했을 때 최적의 경우를 출력한다.

예제 입력 1

8
2
5
7
6
9
8
4
2

예제 출력 1

5

예제 입력 2

8
9
1
6
2
6
5
8
3

예제 출력 2

5

출처

  • 잘못된 조건을 찾은 사람: jh05013