31796번 - 한빛미디어 (Easy)

문제

이 문제는 "한빛미디어(Hard)" 문제와 입력 조건과 출력 조건이 다르다.

한빛미디어(주)는 '책으로 여는 IT 세상'을 만들어 갑니다. IT 세상의 주역은 '우리' 입니다. 한빛미디어(주)는 IT 세상의 주역들을 위한 프로그래밍, 컴퓨터공학, IT 에세이, Make, 리얼타임(전자책), OA, 그래픽, 나와 내 아이를 위한 실용 등 다양한 분야의 책으로 IT 세상을 만들어 가고 있습니다.

대학교를 졸업한 산지니는 2022년부터 부산대학교 프로그래밍 대회의 후원사를 맡아온 한빛미디어의 의뢰를 받았다. 바로 한빛미디어가 출판한 책들의 데이터베이스를 이용한 웹사이트의 책 진열 프로그램을 개발해달라는 의뢰였다. 산지니는 기쁜 마음으로 의뢰를 승낙했고, 프로그램을 개발하기 시작했다. 데이터베이스의 책들은 아래 규칙에 따라 웹사이트의 페이지에 진열된다.

• 웹사이트의 한 페이지에 책을 한 종류 이상 진열해야 한다.
• 가격이 두 배 이상 차이 나는 책을 한 페이지에 함께 진열할 수 없다. 예를 들어 가격이 3ドル,000円$원인 책은 5ドル,000円$원인 책과 함께 진열할 수 있지만 6ドル,000円$원인 책과는 함께 진열할 수 없다.

산지니는 책이 진열된 페이지가 많으면 고객이 책을 찾기 힘들 것으로 생각해 책이 진열될 페이지 수를 최소화하기로 했다. 산지니를 도와주자!

입력

첫 번째 줄에 책의 개수를 나타내는 정수 $N$이 주어진다. $(1 \leq N \leq 10^5)$

두 번째 줄에 $i$번째 책의 가격을 나타내는 정수 $S_{i}$가 공백으로 구분되어 주어진다. $(10^3 \leq S_{i} \leq 10^6)$

출력

모든 책을 진열하는 데 필요한 최소 페이지 수를 출력한다.

제한

힌트