시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 83 34 19 33.333%

문제

민호는 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