Gorilla Koko loves to travel through his native jungle with the help of vines.
In total, there are N vines in the jungle, located one after another and numbered from left to right with integers from 1 to N. The distance between adjacent vines is D meters. Being on the i-th liana, Koko can jump from it no more than ai meters to the right. In the process of jumping, Koko should cling to some other vine, which she will fly past.
At the moment, Coco is hanging on the first vine and wants to move as far to the right as possible.
Help Coco and determine the maximum number of creeper she can reach.
Input
The first line of the input contains an integer N (2 ≤ N ≤ 10
5) — number of vines.
The second line contains an integer D (1 ≤ D ≤ 10
9) — distance between adjacent vines.
Each of the next N lines contains an integer ai (1 ≤ a
i ≤ 10
9) — how many meters to the right can Coco jump, being on the i-th liana.
Imprint
Print a single integer — the maximum number of creeper that can reach
Coco.
Examples
| # |
Input |
Output |
| 1 |
5
3
7
8
2
2
6 |
4 |
Remark
In the example from the condition, 5 vines are given, and the distance between the vines is 3 meters. While on the first vine, Koko can jump no more than 7 meters, which means she can jump to the second and third vines. She needs to stop at the second vine, because from the second vine the jump length is 8 meters, and this will allow her to jump to the fourth vine. From the fourth vine, the jump length is 2, which is less than the distance to the next vine, so Coco will stop at the fourth vine.