Special Permutation Generator Ordering

Consider the set of all permutations of 1 through \(n\) (there are \(n!\) in total). Normally, when generating the permutations, they are produced in lexicographical order (with respect to the natural order of numbers). In this problem a generator is used to define a custom lexicographical order over the \(n!\) permutations.

The generator is itself a permutation of \(\{1,2,\dots,n\}\), denoted as \(a_1,a_2,\dots,a_n\). Given two different permutations of \(\{1,2,\dots,n\}\), say \(x_1,x_2,\dots,x_n\) and \(y_1,y_2,\dots,y_n\), we define their order as follows:

1. Find the smallest index \(i\) (\(1 \le i \le n\)) such that \(x_{a_i}\) and \(y_{a_i}\) differ.
2. Now, viewing the generator \(a_1,a_2,\dots,a_n\) as an ordering on the numbers \(1,2,\dots,n\) (i.e. a number \(u\) is considered less than \(v\) if \(u\) appears before \(v\) in the generator), if \(x_{a_i}\) comes before \(y_{a_i}\) in the generator then the permutation \(x_1,x_2,\dots,x_n\) is generated before \(y_1,y_2,\dots,y_n\).

For example, when \(n=3\) and the generator is 1 3 2, the order in which the 6 permutations are generated is:

123
132
321
312
231
213

Now, given a permutation \(p=p_1,p_2,\dots,p_n\) as input, your task is to determine:

• The generator (i.e. a permutation of \(\{1,2,\dots,n\}\)) that makes \(p\) appear as early as possible (i.e. it minimizes the rank of \(p\) among all \(n!\) permutations generated by that generator).
• The generator that makes \(p\) appear as late as possible (i.e. it maximizes the rank).

If there are multiple generators that achieve the optimal (earliest or latest) ranking, output the lexicographically smallest generator (in the usual numerical order of its elements).

Ranking Formula:

For a fixed generator \(a=a_1,a_2,\dots,a_n\), define the ordering on numbers by the positions in \(a\) (i.e. for numbers \(x\) and \(y\), \(x\) is considered less than \(y\) if the index of \(x\) in \(a\) is smaller than the index of \(y\) in \(a\)). Then, if we form the sequence \[ c=(p_{a_1},p_{a_2},\dots,p_{a_n}), \] its lexicographical rank among all \(n!\) permutations (with respect to the order defined by the generator) can be computed by \[ \text{rank}(p;a)=1+\sum_{i=1}^{n} \Big(\#\{\text{unused numbers that come before }p_{a_i}\}\Big)\times (n-i)!. \]

Your program must choose the generator \(a\) that minimizes \(\text{rank}(p;a)\) and the one that maximizes \(\text{rank}(p;a)\) (breaking ties by lexicographical order of \(a\)).

inputFormat

The first line contains a single integer \(n\) (\(1 \le n \le 8\)). The second line contains \(n\) distinct integers \(p_1,p_2,\dots,p_n\) representing a permutation of \(\{1,2,\dots,n\}\), separated by spaces.

outputFormat

Output two lines. The first line is the lexicographically smallest generator (a permutation of \(\{1,2,\dots,n\}\) with elements separated by spaces) that causes the input permutation \(p\) to appear as early as possible. The second line is the lexicographically smallest generator that makes \(p\) appear as late as possible.

sample

3
1 2 3

1 2 3
2 3 1