Codeforces Round 372 (Div. 2) |
---|
Закончено |
Кодер ZS кодит на чокнутом компьютере. Если не вводить слова на протяжении c секунд, то все, что было введено, исчезает!
Формально, если слово ввели в секунду a, а затем следующее в секунду b, то если b - a ≤ c, ко всем словам на экране просто добавляется новое слово. Если же b - a > c, то все, что было на экране, пропадает, и после этого только что введенное слово появляется на экране.
К примеру, если c = 5, а слова вводятся в секунды 1, 3, 8, 14, 19, 20, то в секунду 8 на экране будут 3 слова. После этого все исчезает в секунду 13, так как ничего введено не было. В секунды 14 и 19 еще два слова вводятся, и, наконец-то, в секунду 20 вводится еще одно слово и всего 3 слова присутствуют на экране.
Вам даны моменты времени, когда Кодер ZS вводил каждое слово. Определите, сколько слов присутствует на экране после того, как он закончил вводить все слова.
В первой строке содержится два целых числа n и c (1 ≤ n ≤ 100 000, 1 ≤ c ≤ 109) — количество слов, введенных Кодером ZS, и задержка чокнутого компьютера соответственно.
Следующая строка содержит n целых чисел t1, t2, ..., tn (1 ≤ t1 < t2 < ... < tn ≤ 109), где ti означает секунду, когда Кодер ZS ввел i-ое слово.
Выведите единственное целое положительное число — количество слов на экране после того, как все n слов были введены, иными словами, в секунду tn.
6 5
1 3 8 14 19 20
3
6 1
1 3 5 7 9 10
2
Первый пример разобран в условии.
Во втором примере из условия, после введения первого слова в секунду 1, оно исчезает, так как в следующее слово вводится в секунду 3 и 3 - 1 > 1. Аналогично, только 1 слово будет присутствовать на экране в секунду 9. Затем вводят слово в секунду 10, так что на экране останутся два слова, так как раннее из них не исчезнет, ведь 10 - 9 ≤ 1.
Название |
---|