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

Пенчик и его друг Кохане путешествуют по Индонезии, и следующая их остановка — Сурабая!

В шумных продуктовых лавках Сурабайи Коханэ купил $$$n$$$ палочек для сатэ и выложил их в линию, причем $$$i$$$-я палочка для сатэ имеет длину $$$p_i$$$. Известно, что $$$p$$$ — перестановка$$$^{\text{∗}}$$$ длины $$$n$$$.

Пенчик хочет отсортировать палочки для сатэ в порядке возрастания их длины, так, чтобы выполнялось $$$p_i=i$$$ для всех $$$1\le i\le n$$$. Для развлечения они придумали правило: они могут менять местами только соседние палочки для сатэ, длина которых отличается ровно на $$$1$$$. Формально, они могут выполнить следующую операцию любое количество раз (возможно, ноль):

  • Выбрать индекс $$$i$$$ ($$$1\le i\le n-1$$$) такой, что $$$|p_{i+1}-p_i|=1$$$;
  • Поменять местами $$$p_i$$$ и $$$p_{i+1}$$$.

Определите, можно ли отсортировать перестановку $$$p$$$, а значит и палочки для сатэ, выполнив вышеописанную операцию некоторое количество раз.

$$$^{\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 2\cdot 10^5$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2\cdot 10^5$$$) — количество палочек для сатэ.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — перестановка $$$p$$$, представляющая длины палочек для сатэ.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.

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

Для каждого набора входных данных выведите «YES», если можно отсортировать перестановку $$$p$$$ с помощью данных операций. В противном случае выведите «NO».

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Пример
Входные данные
2
4
2 1 3 4
4
4 2 3 1
Выходные данные
YES
NO
Примечание

В первом наборе входных данных мы можем отсортировать перестановку $$$p = [2, 1, 3, 4]$$$, выполнив операцию над индексом $$$1$$$ ($$$|p_2 - p_1| = |1 - 2| = 1$$$), в результате чего получим $$$p = [1, 2, 3, 4]$$$.

Для второго набора входных данных можно доказать, что перестановку $$$p = [4, 2, 3, 1]$$$ невозможно отсортировать данными операциями. Для примера приведём последовательности операций, которые можно выполнить над перестановкой:

  • Выбрать $$$i = 2$$$ ($$$|p_3 - p_2| = |3 - 2| = 1$$$). В результате получится $$$p = [4, 3, 2, 1]$$$.
  • Выбрать $$$i = 1$$$ ($$$|p_2 - p_1| = |3 - 4| = 1$$$). В результате получится $$$p = [3, 4, 2, 1]$$$.
  • Выбрать $$$i = 3$$$ ($$$|p_4 - p_3| = |1 - 2| = 1$$$). В результате получится $$$p = [3, 4, 1, 2]$$$.

К сожалению, после выполнения этих операций перестановка $$$p$$$ останется неотсортированной.