Problem F: Fencing Hall

Problem F: Fencing Hall

Time Limit: 2 Sec  Memory Limit: 128 MB
Submit: 2697  Solved: 565
[Submit][Status][Web Board]

Description

Dateri has a magic sequence and LowbieH is interested in it. Dateri promises that if LowbieH can answer his question, then he will play fencing with LowbieH. We denote the magic sequence by \(\{a_n\}\) and Dateri will choose a lucky number \(k\). He asks LowbieH to find length of the longest consecutive subsequence such that the absolute difference between any two number in the subsequence should not exceed \(k\). Can you help LowbieH?

Input

The first line contains two integers \(k(0 \leq k \leq 2*10^9)\) and \(n(1 \leq n \leq 3 * 10^6)\).

The second line contains \(n\) integers \(a_1,\cdots,a_n(1 \leq a_i \leq 2 * 10^9,\ 1 \leq i \leq n)\).

Output

One line contains the answer, i.e. the length of the longest available consecutive subsequence.

Sample Input

3 9
5 1 3 5 8 6 6 9 10

Sample Output

4

HINT


There are two available consecutive subsequences : \(\{5,8,6,6\}\) and \(\{8,6,6,9\}\).

[Submit][Status]