CF2231B.Another Sorting Problem

You are given an array $a_1, a_2, \ldots, a_n$. You can perform the following operation on this array at most once:

• Choose a positive integer $k$, as well as a subsequence $b_1, b_2, \ldots, b_m$ of the array $a$$^{\text{∗}}$ and add $k$ to each element of this subsequence, that is, for each $i$ perform $a_{b_i} := a_{b_i} + k$.

You need to determine whether it is possible to sort the array in nondecreasing order by performing this operation at most once.

$^{\text{∗}}$A sequence $b$ is a subsequence of a sequence $a$ if $b$ can be obtained from $a$ by the deletion of several (possibly, zero or all) element from arbitrary positions.

给你一个数组 $a_1, a_2, \ldots, a_n$。你最多可以对这个数组执行以下操作一次：

• 选择一个正整数 $k$，以及数组 $a$ 的一个子序列 $b_1, b_2, \ldots, b_m$$^{\text{∗}}$，并将 $k$ 加到该子序列的每个元素上，即对每个 $i$ 执行 $a_{b_i} := a_{b_i} + k$。

你需要判断：是否可以通过最多执行一次该操作，将数组排序为非递减顺序。

$^{\text{∗}}$ 序列 $b$ 是序列 $a$ 的一个子序列，当且仅当 $b$ 可通过从 $a$ 中任意位置删除若干（可能为零个或全部）元素而得到。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

In the first line of each test case, one integer $n$ is given ($1 \leq n \leq 2 \cdot 10^5$) — the length of the array $a$.

In the second line of each test case, $n$ integers $a_1, a_2, \ldots, a_n$ are given ($1 \leq a_i \leq 10^9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, print "Yes" if it is possible to sort the array by performing the operation at most once. Otherwise, print "No". You may print the answer in any case. For example, "YeS", "YES", "NO", "nO" will also be accepted.

对于每个测试用例，如果可以通过至多执行一次该操作将数组排序，则输出“Yes”；否则输出“No”。你可以以任意大小写形式输出答案。例如，“YeS”、“YES”、“NO”、“nO”均被接受。

In the first test case, the array is already sorted, so the operation does not need to be performed at all.

In the second test case, it can be shown that it is impossible to sort the array using such an operation.

In the third test case, choose $k = 6$ and choose the subsequence $[2, 4, 6]$ as $b$. Then after this operation, the array $a$ becomes $[8, \textbf{9}, 9, \textbf{10}, 10, \textbf{11}, 11]$ (the elements of the chosen subsequence are shown in bold).

在第一个测试用例中，数组已经有序，因此完全不需要执行该操作。

在第二个测试用例中，可以证明无法通过此类操作将数组排序。

在第三个测试用例中，选择 $k = 6$，并选择子序列 $[2, 4, 6]$ 作为 $b$。执行该操作后，数组 $a$ 变为 $[8, \textbf{9}, 9, \textbf{10}, 10, \textbf{11}, 11]$（所选子序列的元素以粗体显示）。