给你一个数组 $$$a_1, a_2, \ldots, a_n$$$。您最多可以对该数组执行一次以下操作:
- 选择一个正整数$$$k$$$,以及数组$$$a$$$$$^{\text{∗}}$$$的子序列$$$b_1, b_2, \ldots, b_m$$$,并将$$$k$$$添加到这个子序列的每个元素上,即对于每个$$$i$$$执行$$$a_{b_i} := a_{b_i} + k$$$。
您需要确定是否可以对数组进行排序 非递减 通过最多执行一次此操作来订购。
$$$^{\text{*}}$$$ 序列 $$$b$$$ 是序列 $$$a$$$ 的子序列,如果 $$$b$$$ 可以通过从任意位置删除几个(可能是零个或全部)元素从 $$$a$$$ 获得。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
在每个测试用例的第一行,给出一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 数组 $$$a$$$ 的长度。
在每个测试用例的第二行中,给出了 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印“是"如果可以通过最多执行一次操作对数组进行排序。否则,打印"No“。您可以在任何情况下打印答案。例如,”是的", "是", "NO", "nO”也将被接受。
示例
输入复制
841 2 3 4510 5 9 4 478 3 9 4 10 5 1165 3 10 5 9 732 1 152 1 1 2 133 1 252 1 2 3 1
输出复制
YESNOYESNOYESYESYESNO
注意
在第一个测试用例中,数组已经排序,因此根本不需要执行该操作。
在第二个测试用例中,可以表明不可能使用这样的操作对数组进行排序。
在第三个测试用例中,选择 $$$k = 6$$$ 并选择子序列 $$$[2, 4, 6]$$$ 作为 $$$b$$$。然后,经过此操作,数组 $$$a$$$ 变为 $$$[8, \textbf{9}, 9, \textbf{10}, 10, \textbf{11}, 11]$$$ (所选子序列的元素以粗体显示)。