У Пети изначально был массив \(a\) целых чисел от \(1\) до \(n\), где \(a[i]=i\).
Он последовательно произвёл \(n\) операций. В итоге он получил новое состояние массива \(a\).
На \(i\)-й операции Петя выбирал первые \(i\) элементов массива и произвольное количество раз совершал их циклический сдвиг вправо (элементы с номерами \(i+1\) и больше оставались на своих местах). Один циклический сдвиг вправо — это такое преобразование, что массив \(a=[a_1, a_2, \dots, a_n]\) станет равен \(a = [a_i, a_1, a_2, \dots, a_{i-2}, a_{i-1}, a_{i+1}, a_{i+2}, \dots, a_n]\).
Например, если \(a = [5,4,2,1,3]\) и \(i=3\) (то есть это третья операция), то в результате этой операции он мог получить любой из трёх массивов:
- \(a = [5,4,2,1,3]\) (делает \(0\) циклических сдвигов или любое количество, которое делится на \(3\));
- \(a = [2,5,4,1,3]\) (делает \(1\) циклический сдвиг или любое количество, которое имеет остаток \(1\) при делении на \(3\));
- \(a = [4,2,5,1,3]\) (делает \(2\) циклических сдвига или любое количество, которое имеет остаток \(2\) при делении на \(3\)).
Рассмотрим пример. Пусть \(n=6\), то есть изначально \(a=[1,2,3,4,5,6]\). Возможный вариант развития событий описан ниже.
- \(i=1\): сколько бы циклических сдвигов Петя не производил, массив \(a\) не изменится.
- \(i=2\): допустим Петя решил сделать \(1\) циклический сдвиг, тогда массив примет вид \(a = [\textbf{2}, \textbf{1}, 3, 4, 5, 6]\).
- \(i=3\): допустим Петя решил сделать \(1\) циклический сдвиг, тогда массив примет вид \(a = [\textbf{3}, \textbf{2}, \textbf{1}, 4, 5, 6]\).
- \(i=4\): допустим Петя решил сделать \(2\) циклических сдвига, тогда массив примет вид \(a = [\textbf{1}, \textbf{4}, \textbf{3}, \textbf{2}, 5, 6]\).
- \(i=5\): допустим Петя решил сделать \(0\) циклических сдвигов, тогда массив не изменится.
- \(i=6\): допустим Петя решил сделать \(4\) циклических сдвига, тогда массив примет вид \(a = [\textbf{3}, \textbf{2}, \textbf{5}, \textbf{6}, \textbf{1}, \textbf{4}]\).
Вам задано финальное состояние массива \(a\) после всех \(n\) операций. Определите, существует ли способ выполнения операций, который приведёт к этому результату. В случае положительного ответа найдите количество циклических сдвигов, которое могло быть сделано во время каждой из \(n\) операций.
Выходные данные
Для каждого набора входных данных выведите ответ на отдельной строке.
Выведите -1, если заданное финальное значение \(a\) нельзя получить, производя произвольное количество циклических сдвигов на каждой операции. Иначе выведите \(n\) неотрицательных целых чисел \(d_1, d_2, \dots, d_n\) (\(d_i \ge 0\)), где \(d_i\) обозначает, что во время \(i\)-й операции первые \(i\) элементов массива были циклически сдвинуты вправо \(d_i\) раз.
Если возможных ответов несколько выведите тот, где суммарное количество сдвигов минимально (то есть сумма значений \(d_i\) наименьшая). Если таких ответов несколько, то выведите любой из них.
Примечание
Первый набор входных данных совпадает с примером из условия.
Второй набор входных данных как видно несложный. Заметим, что ответ \([3, 2, 1]\) также даёт ту же перестановку, но так как суммарное количество сдвигов \(3+2+1\) больше \(0+0+1\), то такой ответ не является правильным.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
6
3 2 5 6 1 4
3
3 1 2
8
5 8 1 3 2 6 4 7
|
0 1 1 2 0 4
0 0 1
0 1 2 0 2 5 6 2
|