题目内容

货架上从左到右有 $n$ 个隔间，第 $i$ 个隔间的承重值为 $a_i$。这些承重值已经排成非严格递增序列，即 $a_1 \le a_2 \le \cdots \le a_n$。

你最多做一次扰动：选定连续区间 $[L,R]$，对区间内第 $i$ 个隔间的承重增加 $(R-i+1)\times m$。也就是说，越靠左增加得越多，最右端只增加 $m$。

扰动后希望出现某一对相邻隔间满足 $a_j > a_{j+1}$。请给出能达成该目标的最短区间长度 $R-L+1$；若无论怎样扰动都无法达成，输出 -1。

约束：测试组数不超过 10^4，单组隔间个数不超过 2\times 10^5，增量基数 $m$ 不超过 10^9。

输入描述

第一行包含一个整数 $T$，表示测试组数。保证 $1 \le T \le 10^4$。 每组数据格式如下： 第一行包含两个整数 $n$ 和 $m$，分别表示隔间个数与增量基数。保证 $2 \le n \le 2 \times 10^5$，$1 \le m \le 10^9$。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$，表示各隔间的承重值，且满足 $a_1 \le a_2 \le \cdots \le a_n$。

输出描述

对每组数据输出一行一个整数：能制造相邻逆序的最短区间长度；若无法做到，输出 -1。

样例1

输入

1
2 5
1 1

输出

1

说明

两个隔间承重相同，差值为 0，小于 $m=5$。 选长度为 1 的区间给左侧加 5，得到 $6>1$，答案为 1。这是 $n=2$ 的边界情形。

样例2

输入

1
3 1
1 3 5

输出

-1

说明

相邻差值分别为 2 和 2，都不小于 $m=1$。 无论怎样扰动都无法让某一对相邻隔间逆序，输出 -1。

样例3

输入

1
2 5
2 2

输出

1

说明

按题意模拟计算得到。