Frog in the Loop: Optimal Edge Reordering

A little frog is trapped in a loop. The loop can be viewed as a cycle with \(n\) vertices (where \(n\) is odd). Each vertex \(i\) has a weight \(a_i\), and for each edge connecting vertex \(i\) and vertex \(i+1\) (for \(1 \le i < n\)) and the edge connecting vertex \(n\) and vertex \(1\), the edge weight is given as \(w_i\) (with \(w_n\) for the edge connecting \(n\) and \(1\)).

These vertex and edge weights are linked by the following relationship: for every edge \(i\), \[ w_i = \frac{1}{2}(a_i + a_{i+1}) \quad (1 \le i < n), \quad \text{and} \quad w_n = \frac{1}{2}(a_n + a_1). \]

If the weight of any edge is changed, then all vertex weights change accordingly until the above relations are satisfied.

The frog has the values \(w_1, \dots, w_n\) and is allowed to arbitrarily swap (i.e. permute) the edge weights any number of times. He wishes to provide two arrangements for \(w_1, \dots, w_n\) such that the resulting vertex weight \(a_1\) is maximized in the first arrangement and minimized in the second arrangement.

Hint: By repeatedly applying the relations, you can deduce that \(a_1\) in terms of the edge weights in the order \(w_1, w_2, \dots, w_n\) is given by:

[ a_1 = w_1 - w_2 + w_3 - w_4 + \cdots + w_n]

Since \(n\) is odd, there is a unique value for \(a_1\) for any permutation of the edge weights. To maximize \(a_1\), you should assign the largest weights to the positions with a positive sign (i.e. the odd positions) and the smallest weights to the negative sign positions (even positions). Similarly, for minimizing \(a_1\), assign the smallest weights to odd positions and the largest weights to even positions.

inputFormat

The first line contains an odd integer \(n\) (\(1 \leq n \leq 10^5\)), the number of edges on the cycle. The second line contains \(n\) space-separated integers \(w_1, w_2, \dots, w_n\) (each \(w_i\) is an integer and \(0 \le w_i \le 10^9\)).

outputFormat

Output two lines. The first line should contain a permutation of the given \(w_i\) that maximizes the computed vertex weight \(a_1 = w_1 - w_2 + w_3 - \cdots + w_n\). The second line should contain a permutation that minimizes \(a_1\). Each line must list \(n\) numbers separated by a single space.

sample

3
1 5 3

5 1 3
1 5 3