题面描述

• 给定一个非降数组 $a={a_1,a_2,\ldots,a_n}$（满足 $a_1\le a_2\le\cdots\le a_n$）。
• 允许至多一次操作：选择区间 $[l,r]$（$1\le l\le r\le n$），对任意 $i\in[l,r]$，令 $a_i\leftarrow a_i+(r-i+1)\cdot m$。
• 目标：使操作后存在某个 $j$ 满足 $a_j>a_{j+1}$。求所需区间长度 $r-l+1$ 的最小值；若不可能则输出 $-1$。

思路

• 对区间内部相邻对 $i,i+1$（$l\le i<r$），操作后有

题目内容

给定一个长度为 $n$ 的数组 {$a_1,a_2,...,a_n$} ，且满足 $a_1≦a_2≦a_n$ 。

你可以至多进行一次以下操作：

选择一个区间 $[l,r] (1 ≦l≦r≦n)$ ，对区间内每个 $i(1≦i≦r)$ ,将 $a_i$ 变成 $a_i+(r-i+1)×m$ 。

请问：为了使操作后数组存在 $j$ 使得 $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$ 个整数 $a_1,a_2,...,a_n(1≦a_i≦10^9)$ 。

此外，保证所有测试数据中 $\sum n≦2×10^5$ 。

输出描述

对于每组测试数据，输出一个整数，表示所求的最小区间长度；如果无法通过一次操作使数组不再保持非严格递增，输出 $-1$ 。

样例1

输入

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

输出

1
-1

说明

在第一个测试中，可选择区间 $[2,2]$ ，此时 $a_2←2+(2-2+1)×2=4$，数组变为 ，满足非严格递增，区间长度为 $1$ 。