Algorithm of Professor Ivanov#5616

Algorithm of Professor Ivanov

1 second

64 megabytes

Very easy

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

\textbf{for } j := 0 \textbf{ to } n - 1 \textbf{ do}

begin

if p_{j} = a then

\ \ \textbf{if } p_j = a \textbf{ then}

k := j

\ \ \ \ k := j

end

swap (k, (k + p_{k}) mod n);

\textbf{swap}(k, (k + p_k) \bmod n);

end;

The function $swap (i, j)$ \textbf{swap}(i, j) swaps the elements $p_{i}$ p_i and $p_{j}$ p_j.

Professor Ivanov claims that any permutation $p_{0}, \dots, p_{n - 1}$ p_0, \ldots, p_{n-1} of the integers $1, \dots, n$ 1, \ldots, n can be sorted in ascending order using several calls of the function $change$ . All you need is to choose, for each call of the function, the correct integer argument $a$ in the range from $1$ to $n$ .

Professor Petrov trusts his colleague, but he does not fully understand the algorithm. Therefore, he proposed a permutation $p_{0}, \dots, p_{n - 1}$ p_0, \ldots, p_{n-1} and asked Professor Ivanov to sort it in ascending order using the function $change$ .

Input

The first line contains an integer $n$ ( $1 \leq n \leq 500$ 1 \leq n \leq 500). The second line contains the permutation $p_{0}, \dots, p_{n - 1}$ p_0, \ldots, p_{n-1} of the integers from $1$ to $n$ , proposed by Professor Petrov.

Output

If Professor Ivanov cannot sort the given permutation using the function $change$ , print "Impossible". Otherwise, print an integer $m$ ( $0 \leq m \leq 1 0^{6}$ 0 \leq m \leq 10^6) on the first line — the number of calls to the function. On the next $m$ lines, print the argument $a$ ( $1 \leq a \leq n$ 1 \leq a \leq n) that should be used in each call. It is guaranteed that if it is possible to sort the given permutation, it can be done in no more than $1 0^{6}$ 10^6 function calls.

Examples

Example 1

Loading

for j := 0 to n - 1 do

if p_{j} = a then

k := j

swap (k, (k + p_{k}) mod n);

swap (i, j)

p_{i}

p_{j}

p_{0}, \dots, p_{n - 1}

1, \dots, n

p_{0}, \dots, p_{n - 1}

1 \leq n \leq 500

p_{0}, \dots, p_{n - 1}

0 \leq m \leq 1 0^{6}

1 \leq a \leq n

1 0^{6}