ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural FU contest. Kontur Cup. Petrozavodsk training camp. Winter 2013

About     Problems     Submit solution     Judge status     Standings
Contest is over

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

Sample

inputoutput
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
To submit the solution for this problem go to the Problem set: 1958. Algorithm of Professor Ivanov