Расстроившись после такого отношения Насти, Денис был очень грустным. Ничего не могло развеселить отвергнутого парня. Чтобы хоть как-то развеселиться он решил побродить по подворотням. И, как ни странно, ему улыбнулась удача! Зайдя в первый двор, он встретил странного человека, который чем-то торговал.
Оглядевшись вокруг, Денис подошел к незнакомцу и купил загадочный товар. Им оказался... Генератор случайных перестановок! Именно это мальчик так давно искал!
Придя домой он стал изучать, как работает его генератор и узнал алгоритм. Процесс генерации перестановки состоит из \(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\) и решил узнать, могла ли она получится в результате работы генератора.
К сожалению, эта задача оказалась слишком сложна для него, и он обратился за помощью к вам. Нужно определить, могла ли получиться выписанная перестановка применением описанного алгоритма, если генератор всегда выбирает нужную Денису позицию.
Примечание
Промоделируем работу генератора на первом тесте.
На \(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\), то есть генератор мог её сгенерировать.