解题思路
给定非严格递增数组 a1≤a2≤⋯≤an，允许至多一次操作：选择区间 [l,r]（长度 L=r−l+1），对每个 i∈[l,r] 执行
ai←ai+k⋅(r−i+1).
这是一个公差为 −k 的等差增量，左端点的增量最大，为 kL。
P4304.第2题-非严格递增数组
题目内容
给定一个长度为 n 的非严格递增数组 a1≤a2≤...≤an 。你可以执行以下操作至多一次：
选择区间 [l,r] ，对每个 i∈[l,r] 执行 ai←ai+k×(r−i+1) ，其中 k 是给定的固定参数。
请找出能使操作后数组极差(最大值与最小值之差) 超过d 的最小区间长度(可以为 0 )。若无法达成，输出 −1 。
【名词解释】
- 极差:数组最大值与最小值的差值，例如数组 {2,5,7} 的极差为 5 .
输入描述
第一行输入 T(1≦T≦104) 表示测试组数。
每组数据包含:
第一行三个整数 n,d,k(2≦n≦2×105,0≦d≦1012,1≦k≦109)
第二行 n 个非严格递增整数 a1,a2,...,an(1≦ai≦109)
保证所有测试数据 ∑n≦2×105 。
输出描述
每组数据输出一个整数，表示满足条件的最小区间长度。
样例1
输入
3
4 5 2
1 3 5 7
3 10 1
2 6 8
3 8 5
1 2 3
输出
0
-1
2
