M. 数列

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

P3512 [POI 2010]

给定 $n, k$ 和一个长度为 $n$ 的序列，求最长的最大值最小值相差不超过 $k$ 的子段。

第一行两个由空格隔开的整数 $k, n$ （ $0\leq k\leq 2\times 10 ^ 9$ ， $1\leq n\leq 3\times 10 ^ 6$ ）， $k$ 表示设定的极差的最大值， $n$ 表示序列的长度。

第二行 $n$ 个由空格隔开的整数 $a_i$ （ $1\leq a_i\leq 2\times 10^ 9$ ）表示序列。

一个整数表示符合条件的子段的长度最大值。

3 9
5 1 3 5 8 6 6 9 10

样例解释： $5, 8, 6, 6$ 和 $8, 6, 6, 9$ 都是满足条件长度为 $4$ 的子段。