2013 Petrozavodsk, February 2
Algorithm of Professor Ivanov
Professor Ivanov has told professor Petrov about a new sorting algorithm, based on the following function 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; |
Function swap(i, j) swaps two elements p_{i} and p_{j}.
Professor Ivanov states that any permutation p_{0}, …, p_{n−1}, of integers 1, ..., n, can be sorted in ascending order with several calls of function change. All you need is to find for each call of function change right integer argument a in limits from 1 to n.
Professor Petrov trusts to his colleague, but he hasn’t understood the algorithm well. So he has suggested a permutation p_{0}, …, p_{n−1} and asked professor Ivanov to sort it in ascending order using function change.
Input
The first line of input contains an integer n (1 ≤ n ≤ 500). The second line contains the permutation p_{0}, …, p_{n−1} of integers 1 to n, suggested by professor Petrov.
Output
If professor Ivanov can’t sort the given permutation using function change print "Impossible". Otherwise, on the first line print integer m: the number of calls to the function (0 ≤ m ≤ 10^{6}). On the next m lines, output argument a that should be used in each call (1 ≤ a ≤ n). It is guaranteed that if it is possible to sort the given permutation, it can be done in no more than 10^{6} function calls.
5 1 3 5 2 4
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