### PROBLEM LINK:

**Author:** Hasan Jaddouh

**Tester:** Misha Chorniy

**Editorialist:** Suchan Park

### DIFFICULTY:

Cakewalk

### PREREQUISITES:

None

### PROBLEM:

There are N hills in a row. The height of the i-th hill is H[i]. Chef is initially on the 1st hill.

When Chef is at hill i, Chef can jump to the adjacent hill j if and only if H[i] - D \le H[j] \le H[j] + U without a parachute, and H[j] < H[i] with a parachute. Chef is allowed to use the parachute *at most once*.

Find the rightmost hill that the Chef can reach.

### QUICK EXPLANATION:

Simulate the whole process. Use the parachute as late as possible.

### EXPLANATION:

Since the Chef can only jump to the adjacent hill, we can make a `for`

-loop that iterates the current position of Chef.

Using the parachute when the Chef can jump without the parachute is obviously a waste. Therefore the Chef should continuously jump without a parachute as long as he can.

So, we can simulate the whole process using a `for`

loop, like this:

```
for i = 1 to N: // i denotes the position of the Chef
if (i == N) {
// If the Chef is on the rightmost hill,
// there is nothing to do.
}
else if (H[i] - D <= H[i+1] <= H[i] + U) {
// if the Chef is able to jump on his own,
// just jump without a parachute
}
else if (H[i+1] < H[i]) {
// Chef can jump if the parachute is left
if(parachute isn't used) {
Use the parachute.
}else {
Break the loop. (since the Chef cannot jump)
}
}
else {
// Chef cannot jump when the next hill is too high
Break the loop. (since the Chef cannot jump)
}
```

One can check whether the parachute is used or not by setting a boolean-type variable. (true if used, false otherwise)

The answer will be the maximum i visited during the loop.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.