Вам дана перестановка $$$a$$$ длины $$$n$$$$$$^{\text{∗}}$$$.
Вы можете выполнять следующую операцию любое количество раз (возможно, ноль):
Например, когда $$$a=[1,4,2,3,5]$$$, вы можете поменять местами $$$a_2$$$ и $$$a_4$$$, чтобы получить $$$[1,3,2,4,5]$$$, но вы не можете поменять местами $$$a_2$$$ и $$$a_3$$$.
Пожалуйста, определите, можно ли отсортировать последовательность $$$a$$$ в порядке возрастания.
$$$^{\text{∗}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).
Вторая строка каждого набора входных данных содержит $$$n$$$ различных целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le n$$$).
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.
Если $$$a$$$ можно отсортировать в порядке возрастания, выведите «YES» на отдельной строке. В противном случае выведите «NO» на отдельной строке.
Вы можете выводить ответ в любом регистре. Например, строки «yEs», «yes», и «Yes» также будут распознаны как положительные ответы.
251 4 3 2 551 4 2 3 5
YESNO
В первом наборе входных данных $$$a$$$ равно $$$[1,4,3,2,5]$$$. Вы можете отсортировать $$$a$$$ в порядке возрастания, поменяв местами $$$a_2$$$ и $$$a_4$$$. Поэтому ответ «YES».
Во втором наборе входных данных $$$a$$$ равно $$$[1,4,2,3,5]$$$. Невозможно отсортировать $$$a$$$ в порядке возрастания. Поэтому ответ «NO».
| Codeforces Round 1080 (Div. 3) |
|---|
| Закончено |
