Viewing Terraces

Time limit1sMemory limit128 MB

Summary

In a chain of terraces where climbing up costs height difference and descending is free, find the most distinct terraces reachable on k credits without returning to ground.

Level: Medium5 of 10
Topics: Sliding window, Two pointers, Array
Solved: No attempts yet

Problem

In the mountains stand viewing terraces connected by elevators. Going up from a lower terrace to the adjacent, higher terrace costs as many credits as the difference between the two terraces' heights. Going down from a higher terrace to a lower one is free. The terraces form a single chain: from the first terrace you can reach only the second, from the second only the first and the third, and so on.

A tourist holds only $k$ credits. Find the largest number of distinct terraces the tourist can visit in one continuous trip, without ever coming back down to the ground in between. Stepping onto the terrace where the trip begins costs nothing.

Input

The first line contains two integers $n$ and $k$ , separated by a single space ( $1 \le n \le 20000$ , $0 \le k \le 20000$ ). Here $n$ is the number of terraces and $k$ is the number of credits the tourist has.

Each of the next $n$ lines contains the height of one terrace, $h_1, h_2, \dots, h_n$ , one per line. Every height satisfies $1 \le h_i \le 10000$ .

Output

Print a single integer: the largest number of terraces the tourist can visit with $k$ credits.

Examples1

Example 1
Input
```
5 1
4
2
1
2
4
```
Expected output
```
4
```