상현이의 물리학및실험1 실험 대작전

면접 대비

시간 제한1초메모리 제한1024 MB

요약
밀도를 정렬한 뒤, 직전 밀도와의 차가 E보다 크면 새 물질로 세어 물질의 개수를 구한다.
난이도

보통10점 중 4점

유형
정렬, 그리디
정답자
아직 제출이 없습니다

문제

물리학및실험1을 수강하고 있는 상현이는 단일 물질로 이루어진 NN개의 추의 밀도를 측정했다. 각 추는 11부터 NN까지의 번호가 붙어있고, ii번 추의 밀도는 D_iD\_i이다. 이때 밀도를 이용하여 NN개의 추를 구성하고 있는 물질의 개수를 알아내고자 한다. 하지만 밀도 측정이 정확하지 않아 두 추의 밀도 차가 오차 범위 EE 미만이라면 두 추는 같은 물질로 이루어졌다고 판단한다. (예를 들어, 오차 범위가 22라면 밀도가 1010, 1111, 1212, 1313, 1414, 1515인 추들은 모두 같은 물질로 만들어졌다고 판단한다.)

이번에는 상현이가 밤을 새지 않도록 그를 도와 NN개의 추를 구성하고 있는 물질의 개수를 출력하는 프로그램을 작성하자!

입력

첫 번째 줄에 두 개의 정수 N$$(1 \le N \le 2 \times 10^5)과 E$$(1 \le E \le 10^9)이 공백으로 구분되어 주어진다.

두 번째 줄에 NN개의 정수 D_1,D_2,⋯ ,D_ND\_1, D\_2, \cdots, D\_N이 공백으로 구분되어 주어진다. (1≤D_i≤109)(1 \le D\_i \le 10^9)

출력

NN개의 추를 구성하고 있는 물질의 개수를 출력한다.

예제1

  1. 예제 1

    입력
    5 10
    5 29 18 9 35
    
    예상 출력
    2