题目内容

在一个气象观测站，记录了一连串 $n$ 天的日最高气温 $t_1, t_2, \dots, t_n$，已知气温变化是非递减的，即 $t_1 \le t_2 \le \dots \le t_n$。你可以至多进行一次“热浪模拟”：选择一个连续的日期区间 $[l, r]$（$1 \le l \le r \le n$），并对其中每一天 $i$ 执行操作 $t_i \leftarrow t_i + K \times (r - i + 1)$，其中 $K$ 是一个正常数。你的目标是使整个序列的温差（最大值与最小值之差，即 $\max\{t_i\} - \min\{t_i\}$）严格大于给定的阈值 $D$。请计算出达成目标所需的最小区间长度（区间长度定义为 $r - l + 1$，允许操作长度 $0$，即不操作已满足条件时答案为 $0$）。如果无论怎么操作都无法使温差大于 $D$，则输出 $-1$。【数据范围与约定】- 测试用例数 $T$ 不超过 $10^4$。- 序列长度 $n$ 满足 $2 \le n \le 2 \times 10^5$，所有测试数据的 $n$ 总和不超过 $2 \times 10^5$。- 阈值 $D$ 满足 $0 \le D \le 10^{12}$。- 系数 $K$ 满足 $1 \le K \le 10^9$。- 每个温度值 $t_i$ 满足 $1 \le t_i \le 10^9$，且序列非递减。

输入描述

第一行包含一个整数 $T$，表示测试数据组数。接下来每组数据包含两行：第一行包含三个整数 $n, D, K$，第二行包含 $n$ 个整数 $t_1, t_2, \dots, t_n$。

输出描述

对于每组数据，输出一行一个整数，表示所需的最小区间长度；如果无法达成则输出 $-1$。