解题思路

• 本题需要把数组划分成若干连续段，使每段满足：

  1. 段内最大值与最小值之差 ≤ A；
  2. 段长 ≥ B； 并使段数最少。

• 关键算法：

题目内容

多多正在处理一批数据,需要把一条长度为 $n$ ,从左到右依次排列的数组 $a_1,a_2,…,a_n$ 裁剪成若干连续的数据段,用于录入公司的数据分析系统.

数据分析系统对于录入的数据块有两个要求

1.每段数据中的最大值与最小值之差需要 小于等于 $A$ .

2.每段数据的长度需要 大于等于 $B$ .

多多需要将该数组全部划分成若干连续的数据段，并且使得所有数据段都满足数据分析系统的要求.多多想知道,在满足上述条件的情况下,划分后的数据段的数量最少为多少,如果不能将数组全部划分,那么输出 $-1$ .

输入描述

第一行,包含一个正整数 $T(1 ≤ T≤ 3)$ 代表测试数据的组数

对于每组测试数据,分别有两行:

第一行,有三个正整数 $n(1 ≤n≤ 10^5),A(0≤ A≤10^9),B(1 ≤ B≤ 10^5)$ .

第二行,包含 $n$ 个整数,分别表示 $a_1,a_2,...,a_n(-10^9≤a_i≤ 10^9)$

输出描述

对于每组数据,输出一个正整数,代表划分后最少的数据段的数量,如果不存在符合要求的划分,那么输出 -1.

样例1

输入

2
10 5 1
1 2 3 4 5 6 7 8 9 10
5 3 3
10 6 2 4 -1

输出

2
-1

说明

对于第一组数据,可以最少划分为两个数据段:

$(1,2, 3, 4, 5) (6, 7, 8, 9, 10)$

对于第二组数据,无法找出符合要求的划分.