Codeforces Beta Round 6 (Дивизион 2) |
---|
Закончено |
До пятидесятилетия известного писателя Берляева осталось несколько дней. По этому поводу в местной библиотеке решили организовать выставку сочинений известного фантаста. Также было решено, что необходимо выбрать все книги, изданные автором за какой-то интервал времени. Понятно, что если книги будут очень сильно различаться по размерам, то посетителям это не понравится. Поэтому, посовещавшись, организаторы пришли к мнению, что высота самой низкой и самой высокой книг, отобранных для экспозиции, должны отличаться не более чем на k миллиметров.
В библиотеке имеется n томов произведений Берляева, расположенных в хронологическом порядке выпуска в свет. Про каждую книгу известна ее высота в миллиметрах hi. Поскольку юбиляр является очень уважаемым в городе человеком, то организаторы хотят представить на выставке наибольшее число его книг, а также узнать, какие при этом периоды творчества писателя они смогут охватить. Помогите организаторам справиться с этой нелегкой задачей.
В первой строке входных данных записаны через пробел два целых числа n (1 ≤ n ≤ 105) и k (0 ≤ k ≤ 106) — количество произведений писателя Берляева, имеющихся в библиотеке, и максимальная высота, на которую могут отличаться самая низкая и самая высокая книги в экспозиции. Во второй строке содержится n целых чисел, записанных через пробел. Каждое число hi (1 ≤ hi ≤ 106) означает высоту i-ой книги в миллиметрах.
В первую строку выходных данных выведите через пробел два числа a и b. Число a означает наибольшее количество книг, которое организаторы смогут представить на выставке, а число b — количество интервалов времени таких, что в каждый из них писатель Берляев издал a книг, и самая высокая из этих книг превосходит самую низкую не более чем на k миллиметров.
В последующие b строк выведите по два целых числа через пробел — номер первого и последнего тома каждого из искомых периодов творчества Берляева.
3 3
14 12 10
2 2
1 2
2 3
2 0
10 10
2 1
1 2
4 5
8 19 10 13
2 1
3 4
Название |
---|