Marks :10

: 33 | : 1

You are given the following:

An array $$$a$$$ consisting of $$$n$$$ elements and an integer $$$k$$$. For each $$$(1 ≤ i ≤ n)$$$ , perform the following operation exactly one time:

Replace $$$a_i$$$, by $$$a_i + x$$$ where $$$x € [-k, k]$$$ which denotes, $$$x$$$ should lie in the range of $$$-k$$$ and $$$k$$$, both inclusive.

Determine the maximum length of the subsequence of array $$$a$$$, such that all numbers in that subsequence are equal after applying the given operation.

Task

A subsequence of array a is an array that can be derived from array a by removing some elements from it. (maybe none or all of them) Assume 1-based indexing

Example

$$$n = 4$$$

$$$k = 1$$$

Array $$$a = [2, 5, 1, 2]$$$

Approach Applying one operation on indices 1, 2, and 4, with $$$x = 0$$$ to get array $$$a$$$ as $$$[2, 5, 1, 2]$$$.

Applying one operation on index 3, with $$$x = 1$$$ to get array a as $$$[2, 5, 2, 2]$$$

Therefore, the maximum length of the subsequence with equal numbers is 3.

Input

The first line contains two integers, N $$$(1 \le N \le 10^5)$$$ and K $$$(0 \le K \le 10^9)$$$.

The second line contains an array of $$$N$$$ integers, $$$A_1,A_2...A_N$$$ $$$(1 \le A_i \le 10^9)$$$

Output

The maximum length of the subsequence of the array $$$a$$$, such that all numbers in that subsequence are equal after applying the given operation.

Example

Input

4 1 2 5 1 2

Output

3

You need to login to view your submissions.

You need to login to view all submissions.

Loading...

Result : Successful

Loading...

Feel something is wrong with the test cases?

Result : Accepted

Test Cases :

But to **Run** or **Submit** the Problem, you need to Log In.

Your challenge has been submitted successfully.

You will get a response soon via WhatsApp or Email.

Do let us know your issue.