eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Алгоритм професора Іванова

Алгоритм професора Іванова

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Професор Іванов розповів професору Петрову, що придумав новий спосіб сортування. У його основі лежить наступна функція change.

function change(a: integer);

begin

for j := 0 to n - 1 do

begin

if p[j] = a then

k := j

end

swap(k, (k + p[k]) mod n);

end;

Функція swap(i, j) міняє місцями елементи масиву p_i та p_j.

Професор Іванов стверджує, що довільний масив p_0, …, p_{n−1}, який є перестановкою цілих чисел 1, ..., n, можна упорядкувати за зростанням, декілька разів викликавши функцію change. Потрібно лише правильно підібрати для кожного виклику функції у якості її аргументу a ціле число у межах від 1 до n.

Професор Петров вірить колезі, але він не дуже добре зрозумів, як працює алгоритм. Тому він запропонував перестановку p_0, …, p_{n−1} і попросив професора Іванова відсортувати її по зростанням за допомогою функції change.

Вхідні дані

У першому рядку записано ціле число n (1 n 500). У другому рядку записані цілі числа p_0, …, p_{n−1} в межах від 1 до n - перестановка, запропонована професором Петровим.

Вихідні дані

Якщо професор Іванов не зможе за допомогою функції change відсортувати масив p_0, …, p_{n−1} за зростанням, виведіть "Impossible". У протилежному випадку виведіть у першому рядку число m - кількість викликів функції (0 m 10^6). У наступних m рядках виведіть аргументи, які потрібно подавати на вхід функції change. Гарантується, що якщо масив можна відсортувати за зростанням, то це можна зробити не більше ніж за 10^6 викликів функції.

Приклад

Вхідні дані #1
5
1 3 5 2 4
Вихідні дані #1
37
1
1
2
1
1
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
Автор О.Соболєва, Д.Дубльоних
Джерело 2013 Петрозаводск, Зима, Контест Уральского университета, Кубок Контура, Задача H