e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

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 pi and pj.

Professor Ivanov states that any permutation p0, …, pn−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 p0, …, pn−1 and asked professor Ivanov to sort it in ascending order using function change.

Input

The first line of input contains an integer n (1n500). The second line contains the permutation p0, …, pn−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 m106). On the next m lines, output argument a that should be used in each call (1an). It is guaranteed that if it is possible to sort the given permutation, it can be done in no more than 106 function calls.

Time limit 1 second
Memory limit 64 MiB
Input example #1
5
1 3 5 2 4
Output example #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
Author O.Soboleva, D.Dublennykh
Source 2013 Petrozavodsk, Winter, Ural FU contest, Kontur Cup, Problem H