题解

• 题面简述：给定一个非严格递增数组 $a_1 \leq a_2 \leq \cdots \leq a_n$，可以选择一个区间 $[l, r]$ 对每个元素执行一次操作。我们的目标是在操作后使得至少存在一个位置 $1 \leq j < n$ 使得 $|a_j - a_{j+1}| > d$，并求出满足条件的最小区间长度 $r - l + 1$，如果无法实现则输出 $-1$。

• 思路：

  1. 计算相邻差 $x_i = a_{i+1} - a_i$ （对于 $i \in [1, n-1]$）。我们需要检查是否存在满足条件的相邻差。
  2. 若存在 $x_i > d$，则无需操作，答案为 $0$。
  3. 如果不存在这样的相邻差，但存在任何 $x_i + m > d$，或者当 $m > d + \min(x)$ 时，答案为 $1$。

题目内容

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

选择区间 $[l,r]$ 对，对每个 $i∈[l,r]$ 执行

• $a_i←a_i+m×(r-i+1)$ ，换句话说，将下标在 $l$ 到 $r$ 区间内的每一个元素都加上 $m×(r-i+1)$ 。

请求出使得操作后数组存在至少一个位置 $1≤j<n$ 满足 $|a_j-a_{J+1}|>d$ 的最小区间长度(可以为 $0$ )。若无法实现，输出 $-1$ 。

【名词解释】

非严格递增数组：对于任意 $1 ≦i< n$ ，都有 $a_i≦ a_{i+1}$ 。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1 ≦T ≦ 10^4)$ 代表数据组数，每组测试数据描述如下：

第一行三个整数

$n,d,m(2≤n≤2×10^5,0≤d≤10^{12},1≤m≤10^9)$

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

除此之外，保证单个测试文件的 $n$ 之和不超过 $2×10^5$ 。

输出描述

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

样例1

输入

2
4 3 2
1 2 3 4
3 5 1
2 4 6

输出

2
-1

说明

第一组：其中一种方案为选择区间 $[3,4]$ ，数组变为 {$1,2,7,6$} ，其中 $|2-7|=5>3$ 满足条件。

样例2

输入

3
2 0 1
1 1
4 0 2
1 2 3 5
6 10 4
1 2 2 4 6 9

输出

1
0
3