## Description

You and your crew just successfully landed on Mars, and due to an unforeseen storm you have

evacuated your base and returned to orbit. As your pod was about to dock with your

interplanetary transportation vehicle one of your crew members, Fred, sneezed and ripped out a

section of cables from the wall. This cause your pod to spin out of control and descend towards

Mar’s surface.

Fred sprang into action and begun plugging in the cables. However, Fred did not connect the

correct cables and the pod crashed into the surface…

The simulation terminates and you confront Fred. “It wasn’t me,” he exclaims. You sigh, and

begin writing a program that can help prevent such a disaster from occurring again.

Problem

You are given a list of cables (and their lengths) that were plugged into a wall. The way in which

these cables were plugged in was linear. That is there are exactly n cable and 2n evenly spaced

holes, where each hole is in a single row. Each cable has some integer length which will denote

the number of holes the cable can cross over. You know that each cable was taught before they

were removed. If a cable can cross two holes, then it will have crossed exactly two holes in the

correct configuration. Additionally each hole has exactly one cable end plugged into it.

You need to return to the user the number of different valid configurations, where two

configurations are different, if at least one hole is connected to a different one via the cable

plugged into it. Additionally, print out at least one valid configuration if one exists.

Input Specification

The first line of input is a single positive integer, n (n ≤ 9), representing the number of cables.

The following line will contain n integers representing the number of holes a cable can (and

should) bypass. The number of bypassed holes will be no more than 2n.

Output Specification

The first line of output should contain a single non-negative integer, a, representing the number

of unique, valid wire configurations. If the value of a is positive, then the output will have a

second line. The second line should contain 2n space-separated integers, where the i-th integer

represents the cable length used in the i-th hole.

Input Output Example

Input Output

4

0 1 2 3

6

3 0 0 2 3 1 2 1

3

0 3 3

1

3 3 0 0 3 3

6

0 1 2 3 4 5

0

Explanation

Case 1

There are 6 unique configurations

0 0 2 3 1 2 1 3

0 0 3 1 2 1 3 2

1 2 1 3 2 0 0 3

2 3 1 2 1 3 0 0

3 0 0 2 3 1 2 1

3 1 2 1 3 2 0 0

Case 2

There is only one unique solution. Note that having the arrangement

31 32 0 0 31 32

is equivalent to having

32 31 0 0 32 31

Thus there is exactly one solution.

Case 3

There is no valid solutions that keeps every cable with a longest possible length, so the answer is

0. There is no second line of output, because there is no valid arrangement.

Grading Information

Read/write in from standard input/output – 5 points

Comments, variable names, whitespace usage – 15 points

Permute the cables using recursion – 10 points

Use a permutation to place cables meaningfully – 10 points

Check the validity of an arrangement – 10 points

Your program will be tested on 10 test cases – 5 points each

No points will be awarded to programs that do not compile.

Solutions without recursion will receive a maximum of 50 points