解题思路

题目给定一个长度为 $n$ 的非严格递增数组，因此原数组一定满足：

现在最多进行一次操作，选择一个区间 $[l,r]$，对区间内第 $i$ 个元素加上：

题目内容

给定一个长度为 $n$ 的非严格递增数组，可以至多进行一次操作:选择区间 $[l,r]$，对区间内第 $i$ 个元素加 $(r-i+1)×m$ (越靠左加得越多)。为了使操作后数组存在 $a_j>a_j+1$，需要选择的区间长度 $r-l+1$ 的最小值是多少？无法满足则输出 $-1$。

输入描述

第一行输入一个整数 $T(1≤T≤10^4)$，代表数据组数。随后每组数据:

第一行两个整数 $n,m(2≤n≤2×10^5,1≤m≤10^9)$,

第二行 $n$ 个整数。

输出描述

每组数据输出一个整数:最小区间长度，或 $-1$ 。

样例1

输入

2
4 2
1 2 3 3
3 1
2 6 8

输出

1
-1