You are given an array of N integers, A_{1}, A_{2} ,…, A_{N} and an integer B which denotes that from any index i, you can jump to any of the indices i+1, i+2, …, i+B. Also, if you step on index i, you have to pay A_{i} coins. If A_{i} is -1, it means you can’t land on index i.

You start from index 1, and your aim is to reach index N. Return the path you should take to minimise the number of coins required. If there are multiple paths with same cost, return the lexicographically smallest such path. If its not possible to reach index N return empty array.

**Notes**

- A
_{i}is either > 0(denoting cost) or -1(denoting that it is not possible to land on index i). - You have to pay coins both at starting and ending indices.
- Path a
_{1}, a_{2},…, a_{n}is lexicographically smaller than b_{1}, b_{2},…, b_{m}, if and only if at the first i where a_{i}and b_{i}differ, a_{i}< b_{i}, or if no such`i`

exists, then`n < m`

.

For example,

```
A=[1, 2, 4, -1, 2] and B = 2
The path which requires minimum coins is to start at index 1 and then move to index 3 and then to 5.
So return [1, 3, 5].
```

Another example,

```
A=[1, 2, 4, -1, 2] and B = 1
In this case it is not possible to reach index 5. So return empty array [].
```

NOTE:You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.

- Hints are not available for this problem

Loading...