解题思路

1. 由于可以任意重排，先将数组从小到大排序。一个桶只关心桶内最小值、最大值和元素个数。
2. 对于一个合法桶，若它在排序后选择了若干不连续元素，那么从它的最小值开始取同样数量的连续元素，最大值不会变大，因此仍然合法。所以最优方案可以看作排序数组上的连续分段。
3. 设 $dp_i$ 表示覆盖排序后前 $i$ 个数的最少桶数。若最后一个桶覆盖 $[i,j]$，需要满足：$$j-i+1\le L,\quad a_j-a_i\le D+E\times(j-i)$$
4. 将第二个条件变形。令 $b_k=a_k-E\times k$，则 $[i,j]$ 合法等价于：

题目内容

给定$n$个非负整数$a_1,a_2,\dots,a_n$，你可以在分组前对这些数进行任意重排。

你需要把所有数划分到若干个桶，每个桶内包含若干个数，设某个桶内共有$t$个数，最小值为$m$，则该桶必须满足：

$1 \leq t \leq L$

$M - m \leq D + E \times (t - 1)$

每个数必须且只能属于一个桶，桶与桶之间互不相交，且并集为全部$n$个数，你的目标是使桶的数量尽可能少，请输出最少桶数。

输入描述

每个测试文件包含多组测试数据，第一行输入一个整数 $T(1 \leq T \leq 10^5)$ 表示数据组数，每组测试数据描述如下：

第一行输入四个整数 $n, D, E, L(1 \leq n \leq 2 \times 10^5, 0 \leq D, E \leq 10^9, 1 \leq L \leq n)$。

第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n(0 \leq a_i \leq 10^9)$。

保证所有测试数据的 $n$ 之和不超过 $2 \times 10^5$。

输出描述

对于每组测试数据，输出一行一个整数，表示最少需要多少个桶。

补充说明

样例1

输入

2
7 3 1 3
1 2 3 7 8 10 10
7 0 0 5
5 5 5 6 6 6 6

输出

3
2

说明

第一组数据的一个最优划分为$\left[1,2,3\right], \left[7,8,10\right], \left[10\right]$，因此答案为$3$。 第二组数据中由于$D = 0, E = 0$，同一桶内必须全部相等，最少需要$2$个桶。