Задача 15 из 21

Особенные детали

Время 2 с · память 256 МБ

На производственной линии последовательно обрабатываются детали. Каждая из NN деталей партии получает оценку качества в баллах; оценки сохраняются в журнале в том порядке, в котором детали сходили с линии. По оценкам составляется рейтинг: деталь занимает место с номером RR, если ровно R−1R - 1 деталей имеют больший балл. Одно место могут делить несколько деталей, а некоторые места могут остаться незанятыми.

Особенной считается деталь с оценкой от AA до BB включительно, для которой выполнены два условия: она обработана после детали с самым высоким баллом в партии; оценка детали, обработанной сразу после неё, отличается от её оценки (в ту или иную сторону) не более чем на KK баллов. Последняя деталь в журнале особенной не считается.

Определите наивысшее место в рейтинге, которое занимает особенная деталь, и общее количество особенных деталей в партии.

Входные данные

В первой строке находится число NN — количество деталей в партии (натуральное число, 3<N<100 0003 < N < 100\,000). Во второй строке находятся три натуральных числа, не превышающих 1000: AA и BB (A<BA < B) — границы диапазона оценок и KK — наибольшая допустимая разность оценок. В каждой из следующих NN строк находится оценка одной детали — натуральное число, не превышающее 1000; оценки записаны в том порядке, в котором детали сходили с линии.

Гарантируется, что наибольшую оценку имеет только одна деталь и что в партии есть хотя бы одна особенная деталь.

Выходные данные

Выведите два целых числа: сначала номер наивысшего места в рейтинге, которое занимает особенная деталь (чем меньше номер, тем выше место), затем общее количество особенных деталей.

Примеры

Ввод 1
12
70 90 5
65
72
88
84
91
77
90
85
80
73
88
83
Вывод 1
2 3
Ввод 2
4
70 90 5
1000
70
75
90
Вывод 2
4 1

Примечание

В первом примере после максимальной оценки 91 особенными являются детали с оценками 90, 85 и 88. Оценка 90 занимает место 2, поэтому ответ — 2 3. Во втором особенная только деталь с оценкой 70: следующая оценка 75 отличается ровно на 5, а её место в рейтинге равно 4.

Решение
Загрузка редактора…
Результат появится здесь

Черновик сохраняется в этом браузере.

Ошибка в задаче