408936: GYM103384 4 Путешествие по джунглям

Горилла Коко очень любит путешествовать по своим родным джунглям с помощью лиан.

Всего в джунглях есть $$$N$$$ лиан, расположенных друг за другом и пронумерованных слева направо целыми числами от $$$1$$$ до $$$N$$$. Расстояние между соседними лианами составляет $$$D$$$ метров. Находясь на $$$i$$$-й лиане, Коко может совершить прыжок с нее не более, чем на $$$a_i$$$ метров вправо. В процессе прыжка Коко должна зацепиться за какую-то другую лиану, мимо которой будет пролетать.

В данный момент Коко висит на первой лиане и хочет переместиться как можно дальше вправо. Помогите Коко и определите максимальный номер лианы, до которой она сможет добраться.

Первая стока входных данных содержит целое число $$$N$$$ ($$$2 \leq N \leq 10^{5}$$$) — количество лиан.

Во второй строке записано целое число $$$D$$$ ($$$1 \leq D \leq 10^{9}$$$) — расстояние между соседними лианами.

В каждой из следующих $$$N$$$ строк записано целое число $$$a_i$$$ ($$$1 \leq a_i \leq 10^9$$$) — на сколько метров вправо может прыгнуть Коко, находясь на $$$i$$$-й лиане.

Выведите единственное целое число — максимальный номер лианы, до которой сможет добраться Коко.

Решения, работающие при $$$N \leq 15$$$, будут набирать не менее $$$16$$$ баллов.

Решения, работаюшие при $$$D = 1$$$, будут набирать не менее $$$12$$$ баллов.

Решения, работающие при $$$N \leq 2000$$$, будут набирать не менее $$$56$$$ баллов.

5
3
7
8
2
2
6

4

В примере из условия дано 5 лиан, а расстояние между лианами равно 3 метрам. Находясь на первой лиане, Коко может прыгнуть не более, чем на 7 метров, то есть она сможет допрыгнуть до второй и третьей лианы. Ей нужно остановиться на второй лиане, потому что со второй лианы длина прыжка равна 8 метрам, и это позволит ей допрыгнуть до четвёртой лианы. С четвёртой лианы длина прыжка равна 2 и это меньше, чем расстояние до следующей лианы, поэтому Коко остановится на четвёртой лиане.