Knight Arrangements

Given a list of knights' strengths, your task is to find all valid arrangements such that for every pair of consecutive knights in the arrangement, the absolute difference between their strengths is exactly \(1\). Formally, if the arrangement is \(a_1, a_2, \dots, a_n\), then it must hold that \(|a_i - a_{i+1}| = 1\) for all \(1 \le i < n\). The arrangements should be output in lexicographical order. If there are no valid arrangements, output nothing.

Example: For the input list [3, 1, 2], the valid arrangements are:

• 1 2 3
• 3 2 1

inputFormat

The first line of input contains an integer (n) (1 ≤ (n) ≤ 10) representing the number of knights. The second line contains (n) space-separated integers representing the strengths of the knights.

outputFormat

For each valid arrangement, print a single line with the arrangement as (n) space-separated integers. The arrangements must be printed in lexicographical order. If there are no valid arrangements, do not output anything.## sample

3
3 1 2

1 2 3
3 2 1