Achievements

Interview

Time limit1sMemory limit512 MB

Summary

Given practice days and a budget of paid days, find the longest run of consecutive days where the number of skipped days does not exceed the budget.

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

Problem

Did you know that Greg practices his Swedish skills every day? Well, almost every day.

The app that Greg uses to learn languages gives out achievement badges to keep you engaged with the app. One of the achievements is for the longest streak, i.e., the highest number of consecutive days that Greg practices Swedish. Remember that Greg does not practice every day, so there are gaps. Fortunately, the app allows him to pay for the days where he did not practice and still obtain the achievement.

Given the days when Greg actually practiced his Swedish and the number of days he is willing to pay for, what is the longest streak he can reach?

Input

The input consists of:

One line with two integers n and p (1 ≤ n, p ≤ 2 · 10^5), where n is the number of days Greg practiced with the app and p is the number of days that he is willing to pay for.
One line with n distinct integers d1, . . . , dn (0 ≤ d1 < d2 < . . . < dn ≤ 10^6), the days when Greg actually practiced.

Output

Output the length of the longest streak that Greg can reach when using the paid days in an optimal way.

Examples2

Example 1
Input
```
5 2
3 5 6 10 11
```
Expected output
```
5
```
Example 2
Input
```
2 2018
42 424242
```
Expected output
```
2019
```