您有一系列排成一行的 $$$n$$$ 时钟,其中第 $$$i$$$ 时钟的初始时间是 $$$a_i$$$。在每一秒中,都会按顺序发生以下事件:
- 每个时钟的时间减少$$$1$$$。如果任何时钟的时间达到 $$$0$$$,您将立即失败。
- 您可以选择移动到相邻的时钟或留在当前所在的时钟。
- 您可以将当前时钟的时间重置回其初始值$$$a_i$$$。
请注意,上述事件按顺序发生。如果某个时钟的时间在某一秒达到$$$0$$$,即使你可以移动到这个时钟并重置该时钟的时间,你仍然会输。
您可以从任何时钟开始。确定是否可以无限期地继续这个过程而不丢失。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。
对于每个测试用例,第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 5 \cdot 10^5$$$) — 时钟的数量。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — 时钟上设置的初始时间。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$5\cdot 10^5$$$。
输出
对于每个测试用例,如果可以无限期地继续此过程,则打印“YES”(不带引号),否则打印“NO”(不带引号)。
在任何情况下都可以输出“YES”和“NO”(例如,字符串“yEs”、“yes”和“Yes”将被识别为肯定响应)。
示例
输入 #1
5 2 4 10 2 2 2 3 4 10 5 3 5 3 5 5 12 13 25 17 30
输出 #1
YES NO NO YES YES
注意
在第一个测试用例中,您可以在两个时钟之间来回移动,反复重置它们。
在第三个测试用例中,假设您从时钟 $$$1$$$ 开始并遵循以下策略:
最初,$$$a=[4,10,5]$$$。
1. $$$a$$$ 变为 $$$[3, 9, 4]$$$。您移动到时钟 $$$2$$$ 并重置其时间,结果是 $$$a=[3, 10, 4]$$$。
2. $$$a$$$ 变为 $$$[2, 9, 3]$$$。您移动到时钟 $$$3$$$ 并重置其时间,结果是 $$$a=[2, 9, 5]$$$。
3. $$$a$$$ 变为 $$$[1, 8, 4]$$$。您移动到时钟 $$$2$$$ 并重置其时间,结果是 $$$a=[1, 10, 4]$$$。
4. $$$a$$$ 变为 $$$[0, 9, 3]$$$。您移动到时钟 $$$1$$$,但您输了,因为 $$$a_1$$$ 达到了 $$$0$$$。
可以证明,没有其他策略可以让你无限期地继续这个过程。