B. Очередная задача на сортировку
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a_1, a_2, \ldots, a_n$$$. Вы можете выполнить над этим массивом не более одного раза следующую операцию:

  • Выберите целое положительное число $$$k$$$, а также подпоследовательность $$$b_1, b_2, \ldots, b_m$$$ массива $$$a$$$$$$^{\text{∗}}$$$ и прибавьте к каждому элементу этой подпоследовательности $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите «Yes», если можно отсортировать массив, выполнив операцию не более одного раза. В противном случае выведите «No». Ответ вы можете выводить в любом регистре. Так, например, «YeS», «YES», «NO», «nO» будут также приняты.

Пример
Входные данные
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
Выходные данные
YES
NO
YES
NO
YES
YES
YES
NO
Примечание

В первом наборе входных данных массив уже отсортирован, поэтому операцию можно ни разу не выполнять.

Во втором наборе входных данных можно показать, что такой операцией нельзя отсортировать массив.

В третьем наборе входных данных можно выбрать $$$k = 6$$$, а в качестве $$$b$$$ выбрать подпоследовательность $$$[2, 4, 6]$$$. Тогда после такой операции массив $$$a$$$ станет $$$[8, \textbf{9}, 9, \textbf{10}, 10, \textbf{11}, 11]$$$ (жирным выделены элементы из выбранной подпоследовательности).