Pepperoni

Limits: 2 sec., 512 MiB

This statement was translated automatically from Ukrainian.

Michelangelo ordered a pepperoni pizza from Antonio’s Pizza-Rama. The pizza is divided into \(n\) slices.

The pizza slices have different spiciness levels. The pizza slices are numbered in clockwise order from 1 to \(n\), and the spiciness of the \(i\)-th slice is equal to \(p_i\).

Michelangelo chooses one pizza slice, and, iterating through the pizza slices in clockwise order starting from this slice, writes down the spiciness levels of all pizza slices in his notepad. Then he finds the longest increasing subsequence of the written numbers and eats the corresponding slices, while giving the remaining slices to Leonardo, Raphael, and Donatello.

Find two cyclic shifts of the pizza for which Michelangelo will eat a different number of slices.

Input

The first line contains an integer \(n\) — the number of pizza slices.

The second line contains \(n\) integers \(p_i\) — the spiciness levels of the pizza slices in clockwise order.

Output

In the first line, print \(n\) integers — the first cyclic shift of the permutation \(p\).

In the second line, print \(n\) integers — the second cyclic shift of the permutation \(p\).

It can be shown that the answer to the problem always exists.

Constraints

\(2 \le n \le 5 \cdot 10^5\),

\(p\) is a permutation of integers from \(1\) to \(n\).

Samples

Input (stdin) сopy	Output (stdout) сopy
7 2 6 4 1 3 7 5	2 6 4 1 3 7 5 4 1 3 7 5 2 6

Notes

The longest increasing subsequence is a subsequence of the array elements in which each subsequent element is strictly greater than the previous one, and which has the maximum possible length among all such subsequences.

A sequence \(x\) is called a subsequence of a sequence \(y\) if some number of elements (possibly zero) can be deleted from \(y\) to leave the sequence \(x\).