解题思路

给定非严格递增数组 $a_1\le a_2\le \cdots \le a_n$，允许至多一次操作：选择区间 $[l,r]$（长度 $L=r-l+1$），对每个 $i\in[l,r]$ 执行

这是一个公差为 $-k$ 的等差增量，左端点的增量最大，为 $kL$。

题目内容

给定一个长度为 $n$ 的非严格递增数组 $a_1≤a_2≤...≤a_n$ 。你可以执行以下操作至多一次：

选择区间 $[l,r]$ ，对每个 $i∈[l,r]$ 执行 $a_i←a_i+k×(r-i+1)$ ，其中 $k$ 是给定的固定参数。

请找出能使操作后数组极差(最大值与最小值之差) 超过d 的最小区间长度(可以为 $0$ )。若无法达成，输出 $-1$ 。

【名词解释】

• 极差:数组最大值与最小值的差值，例如数组 {$2,5,7$} 的极差为 $5$ .

输入描述

第一行输入 $T(1 ≦ T ≦ 10^4)$ 表示测试组数。

每组数据包含:

第一行三个整数 $n,d,k(2≦n≦2×10^5,0≦d≦10^{12},1≦k≦10^9)$

第二行 $n$ 个非严格递增整数 $a_1,a_2,...,a_n(1≦a_i≦10^9)$

保证所有测试数据 $\sum n ≦ 2 × 10^5$ 。

输出描述

每组数据输出一个整数，表示满足条件的最小区间长度。

样例1

输入

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

输出

0
-1
2