NOI Contest Archive

Archive / 2021 / April 2021

Knuckles Range

Hard · National Olympiad in Informatics Sri Lanka - April 2021

Knuckles is a mountain range located in the Central province of Sri Lanka. The Tourist Authority of Sri Lanka wants to create an adventures cable car track connecting peaks in the mountain. The authority wants to create a track connecting the maximum possible amount of mountain peaks.

For simplicity assume that mountains are arranged along a straight line. As they want to create the most adventurous cable car track they can connect two mountain peaks only if their altitude difference is at least H. They need to figure out the number of maximum possible peaks that can be used in order to get the budget allocated from the parliament. They asked for your help to calculate the maximum possible number of peaks that can be used.

Note: A cable tract can be connected from jth mountain peak to ith mountain peak only if j < i.

Input Format

Output Format

A single integer denoting the maximum number of possible mountain peaks that can be selected.

Constraints

1 \(\leq\) N \(\leq\) 105

1 \(\leq\) hi \(\leq\) 1015

1 \(\leq\) H \(\leq\) 109

Sample Input 0

5 2
1 3 6 7 4

Sample Output 0

4