1958. Algorithm of Professor Ivanov @ Timus Online Judge

1958. Algorithm of Professor Ivanov

Time limit: 1.0 second
Memory limit: 64 MB

Professor Ivanov has told professor Petrov about a new sorting algorithm, based on the following function change.

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₀, …, 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₀, …, 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₀, …, p_{n − 1} of integers 1, ..., 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⁶). 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⁶ function calls.

Sample

input	output
5 1 3 5 2 4	3 4 3 3

Problem Author: Olga Soboleva (prepared by Denis Dublennykh)
Problem Source: Ural FU contest. Kontur Cup. Petrozavodsk training camp. Winter 2013