Дорога по зданиям


Отправить решение Решать в редакторе

Сложность: 40%
Очки: 100 (частичный балл)
Ограничение по времени: 1.0s
Ограничение по памяти: 256M

Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Дорога по зданиям

В ряд стоят n зданий с высотами h_i. Начиная с первого здания, Эркин переходит на следующее. Если следующее не выше текущего, переход бесплатен. Иначе нужно либо потратить на подъём h_{i+1} - h_i кирпичей, либо использовать одну лестницу (любой высоты). Есть b кирпичей и l лестниц. До какого самого дальнего здания можно добраться?

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

В первой строке числа n, b, l (1 ≤ n ≤ 200000, 0 ≤ b ≤ 10^9, 0 ≤ l ≤ n). Во второй строке n целых чисел от 1 до 10^9.

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

Номер (с единицы) самого дальнего достижимого здания.

Примеры

Пример 1

Ввод:

5 5 1
4 2 7 6 9

Вывод:

5
Пример 2

Ввод:

3 0 0
1 5 9

Вывод:

1
Пример 3

Ввод:

4 0 0
5 4 3 2

Вывод:

4

Комментарии

Еще нет ни одного комментария.