Professor Ivanov has told professor Petrov about a new sorting algorithm,
based on the following function change.
for j := 0 to n - 1 do
if p[j] = a then
k := j
swap(k, (k + p[k]) mod n)
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.
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.
If professor Ivanov can’t sort the given permutation using function change,
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 ≤ a ≤ n).
It is guaranteed that if it is possible to sort the given permutation,
it can be done in no more than 106 function calls.
1 3 5 2 4
Problem Author: Olga Soboleva (prepared by Denis Dublennykh)
Problem Source: Ural FU contest. Kontur Cup. Petrozavodsk training camp. Winter 2013