题目描述

给定一个长度为 $n$ 的数组 $a_1, a_2, \dots, a_n$。你可以对该数组至多执行一次以下操作：

• 选择一个正整数 $k$，以及数组 $a$ 的一个子序列对应的下标集合 $b_1, b_2, \dots, b_m$，并将该子序列中的每个元素加上 $k$。也就是说，对于每个 $i$（$1 \le i \le m$），执行 $a_{b_i} := a_{b_i} + k$。

请判断是否可以通过至多一次上述操作，将数组 $a$ 变成非降序序列。

序列 $b$ 是序列 $a$ 的子序列，当且仅当 $b$ 可以通过删除 $a$ 中任意位置的若干个（可能是零个或全部）元素得到。*

如果一个序列满足对于所有的 $1 \le i < n$，都有 $a_i \le a_{i+1}$ 成立，则称其为非降序序列。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 表示测试用例的数量。

对于每个测试用例：

• 第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$）—— 表示数组 $a$ 的长度。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）—— 表示数组的元素。

输出格式

对于每个测试用例，如果能够通过至多一次操作将数组排序，输出 YES；否则输出 NO。

样例输入 1

8
4
1 2 3 4
5
10 5 9 4 4
7
8 3 9 4 10 5 11
6
5 3 10 5 9 7
3
2 1 1
5
2 1 1 2 1
3
3 1 2
5
2 1 2 3 1

样例输出 1

YES
NO
YES
NO
YES
YES
YES
NO

说明

样例解释

• 在第一个测试用例中，数组已经是非降序排列的，因此完全不需要执行任何操作，输出 YES。
• 在第二个测试用例中，可以证明无论如何操作都无法将数组排序。
• 在第三个测试用例中，可以选择 $k=6$，并选择子序列对应的下标 $b = [2, 4, 6]$（即分别对应元素 $a_2=3, a_4=4, a_6=5$）。执行操作后，数组 $a$ 将变为 $[8, 9, 9, 10, 10, 11, 11]$，它是一个非降序序列。

数据范围

对于所有测试点，保证:

• $1 \le t \le 10^4$。
• $1 \le n \le 2 \times 10^5$。
• $1 \le a_i \le 10^9$。
• 保证同一测试点内所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。
• 保证所有的输入数值均为整数。