问题描述

称连续子数组 $a_l , a_{l+1}, \dots, a_r$ 是彩虹子数组，若 $a_{i+1} − a_i = 1$。

可以进行至多 $k$ 次操作，每次操作可以把一个元素增加或减少 $1$，求操作后最长的彩虹子数组。

输入格式

有多个测试用例。

输入的第一行包含一个整数 $T$ 表示测试用例的数量。对于每个测试用例第一行包含两个整数 $n$ 和 $k$ ($1≤n≤5×10^5, 0≤k≤10^{15}$)，表示序列长度和可执行的最大操作数。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$ ($1≤a_i≤10^9$)，表示序列。

保证所有测试用例的 $n$ 之和不超过 $5×10^5$。

输出格式

对每个测试用例输出一行，其中包含一个整数，表示最多执行 $k$ 次操作后最长彩虹子数组的最大可能长度。

样例

5
7 5
7 2 5 5 4 11 7
6 0
100 3 4 5 99 100
5 6
1 1 1 1 1
5 50
100 200 300 400 500
1 100
3

4
3
5
1
1

样例解释

对于第一个示例测试用例，我们可以执行 $4$ 次操作并将序列更改为 $\{7,3,4,5,6,11,7\}$。最长的彩虹子数组 $\{3,4,5,6\}$，因此答案是 $4$。

对于第二个示例测试用例，我们无法执行任何操作。最长的彩虹子数组是 $\{3,4,5\}$，因此答案是 $3$。

对于第三个示例测试用例，我们可以执行 $6$ 次操作，并将序列更改为 $\{−1,0,1,2,3\}$。整个序列是一个彩虹子数组，因此答案为 $5$。