Расстроившись после такого отношения Насти, Денис был очень грустным. Ничего не могло развеселить отвергнутого парня. Чтобы хоть как-то развеселиться он решил побродить по подворотням. И, как ни странно, ему улыбнулась удача! Зайдя в первый двор, он встретил странного человека, который чем-то торговал.
Оглядевшись вокруг, Денис подошел к незнакомцу и купил загадочный товар. Им оказался... Генератор случайных перестановок! Именно это мальчик так давно искал!
Придя домой он стал изучать, как работает его генератор и узнал алгоритм. Процесс генерации перестановки состоит из $$$n$$$ шагов. На $$$i$$$-м шаге выбирается позиция (индекс) для значения $$$i$$$ $$$(1 \leq i \leq n)$$$. Позиция для значения $$$i$$$ определяется следующим образом:
- Для всех $$$j$$$ от $$$1$$$ до $$$n$$$ посчитаем $$$r_j$$$ — минимальный такой индекс, что $$$j \leq r_j \leq n$$$, a позиция $$$r_j$$$ еще не занята в перестановке. Если таких позиций нет, то будем считать, что значение $$$r_j$$$ не определено.
- Для всех $$$t$$$ от $$$1$$$ до $$$n$$$ посчитаем $$$count_t$$$ — количество таких позиций $$$1 \leq j \leq n$$$, что значение $$$r_j$$$ определено и $$$r_j = t$$$.
- Рассмотрим все еще не занятые позиции перестановки и среди таких рассмотрим позиции, для которых значение в массиве $$$count$$$ максимально.
- Генератор выбирает одну из таких позиций для значения $$$i$$$. Генератор может выбрать любую позицию.
Рассмотрим работу алгоритма на следующем примере:
Пусть $$$n = 5$$$ и алгоритм уже расставил значения $$$1, 2, 3$$$ в перестановке. Рассмотрим, как генератор будет выбирать позицию для значения $$$4$$$:
- Значения $$$r$$$ будут $$$r = [3, 3, 3, 4, \times]$$$, где $$$\times$$$ означает неопределенное значение.
- Тогда значения $$$count$$$ будут $$$count = [0, 0, 3, 1, 0]$$$.
- Есть только две не занятые позиции в перестановке: $$$3$$$ и $$$4$$$. Значение в массиве $$$count$$$ для позиции $$$3$$$ равно $$$3$$$, для позиции $$$4$$$ равно $$$1$$$.
- Максимальное значение достигается только для позиции $$$3$$$, поэтому алгоритм однозначно выберет эту позицию для значения $$$4$$$.
Довольный своим приобретением Денис пошел домой. Несколько дней без перерыва он генерировал перестановки и решил, что преисполнился в осознании процесса генерации. Он считает, что может придумывать случайные перестановки не хуже генератора.
После этого он выписал первую пришедшую на ум перестановку $$$p_1, p_2, \ldots, p_n$$$ и решил узнать, могла ли она получится в результате работы генератора.
К сожалению, эта задача оказалась слишком сложна для него, и он обратился за помощью к вам. Нужно определить, могла ли получиться выписанная перестановка применением описанного алгоритма, если генератор всегда выбирает нужную Денису позицию.
В первой строке записано целое число $$$t$$$ $$$(1 \leq t \leq 10^5)$$$ — количество наборов входных данных в тесте. Далее содержатся сами описания наборов.
В первой строке каждого набора находится единственное целое число $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ — длина перестановки.
Во второй строке набора находится $$$n$$$ различных целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$) — выписанная Денисом перестановка.
Гарантируется, что сумма значений $$$n$$$ по всем входным данным не превосходит $$$10^5$$$.
Выведите «Yes», если эта перестановка могла быть получена в результате работы генератора. В противном случае выведите «No».
Все буквы можно выводить в любом регистре.
5 5 2 3 4 5 1 1 1 3 1 3 2 4 4 2 3 1 5 1 5 2 4 3
Yes Yes No Yes No
Промоделируем работу генератора на первом тесте.
На $$$1$$$ шаге $$$r = [1, 2, 3, 4, 5], count = [1, 1, 1, 1, 1]$$$. Максимальное значение достигается в любой свободной позиции, поэтому генератор может выбрать случайную позицию от $$$1$$$ до $$$5$$$. В нашем примере он выбрал $$$5$$$.
На $$$2$$$ шаге $$$r = [1, 2, 3, 4, \times], count = [1, 1, 1, 1, 0]$$$. Максимальное значение достигается в позициях от $$$1$$$ до $$$4$$$, поэтому генератор может выбрать случайную позицию среди них. В нашем примере он выбрал $$$1$$$.
На $$$3$$$ шаге $$$r = [2, 2, 3, 4, \times], count = [0, 2, 1, 1, 0]$$$. Максимальное значение равно $$$2$$$ и достигается только в позиции $$$2$$$, поэтому генератор выберет эту позицию.
На $$$4$$$ шаге $$$r = [3, 3, 3, 4, \times], count = [0, 0, 3, 1, 0]$$$. Максимальное значение равно $$$3$$$ и достигается только в позиции $$$3$$$, поэтому генератор выберет эту позицию.
На $$$5$$$ шаге $$$r = [4, 4, 4, 4, \times], count = [0, 0, 0, 4, 0]$$$. Максимальное значение равно $$$4$$$ и достигается только в позиции $$$4$$$, поэтому генератор выберет эту позицию.
Итого мы получили перестановку $$$2, 3, 4, 5, 1$$$, то есть генератор мог её сгенерировать.
