您想要建造一个由 $$$n$$$ 相等部分组成的栅栏。所有部分的宽度等于 $$$1$$$,高度等于 $$$k$$$。您将所有部分并排放置在一行中。
不幸的是,栅栏下面的地面并不平坦。为简单起见,您可以认为第 $$$i$$$ 部分下的地面等于 $$$h_i$$$。
建造围栏时应遵循以下几条规则:
1. 连续的部分应具有长度至少$$$1$$$的公共边;
2. 第一个和最后一个部分应位于相应的地面上;
3. 其间的部分可以位于地面或更高,但距地面 $$$h_i$$$ 的高度不得高于 $$$k - 1$$$(高度应为整数);
第一个测试用例的可能围栏之一(蓝色)
是否可以建造符合所有规则的围栏?
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$2 \le k \le 10^8$$$) - 围栏中的部分数量和每个部分的高度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$h_1, h_2, \dots, h_n$$$ ($$$0 \le h_i \le 10^8$$$),其中 $$$h_i$$$ 是第 $$$i$$$ 部分下方的地面水平。
保证测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,如果可以构建满足所有规则的栅栏,则打印“是”。否则,打印NO。
您可以在任何情况下打印每个字母(例如,YES,Yes,yes,yE 都将被识别为肯定答案)。
示例
输入 #1
3 6 3 0 0 2 5 1 1 2 3 0 2 3 2 3 0 2
输出 #1
YES YES NO
注意
在第一个测试用例中,图中显示了一个可能的围栏。
在第二个测试用例中,根据第二条规则,您应该在相应的地面上构建两个部分,并且由于 $$$k = 3$$$、$$$h_1 = 0$$$ 和 $$$h_2 = 2$$$ 也满足第一条规则。
在第三个测试用例中,根据第二条规则,您应该在高度 $$$3$$$ 上构建第一部分,在高度 $$$2$$$ 上构建第三部分。根据第一条规则,第二部分的高度应至少为 $$$2$$$(与第一部分有公共边),但根据第三条规则,第二部分的高度最多可达 $$$h_2 + k - 1 = 1$$$。