Пепероні

Limits: 2 sec., 512 MiB

Мікеланджело замовив піцу пепероні з Antonio’s Pizza-Rama. Піца поділена на \(n\) шматків.

Шматки піци мають різну гостроту. Шматки піци пронумеровані в порядку за годинниковою стрілкою від 1 до \(n\), гострота \(i\)-го шматка рівна \(p_i\).

Мікеланджело обирає один шматок піци, і, перебираючи шматки піци за годинниковою стрілкою починаючи з цього шматка, записує гостроти всіх шматків піци у блокнот. Далі знаходить найдовшу зростаючу підпослідовність записаних чисел і з’їдає відповідні їм шматки, а інші шматки віддає Леонардо, Рафаелю та Донателло.

Знайдіть два циклічні зсуви піци, для яких Мікеланджело з’їсть різну кількість шматків.

Input

У першому рядку задано ціле число \(n\) — кількість шматків піци.

У другому рядку задано \(n\) цілих чисел \(p_i\) — гостроти шматків піци в порядку за годинниковою стрілкою.

Output

У першому рядку виведіть \(n\) цілих чисел — перший циклічний зсув перестановки \(p\).

У другому рядку виведіть \(n\) цілих чисел — другий циклічний зсув перестановки \(p\).

Можна показати, що відповідь на задачу завжди існує.

Constraints

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

\(p\) є перестановкою цілих чисел від \(1\) до \(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

Найдовша зростаюча підпослідовність — це підпослідовність елементів масиву, у якій кожен наступний елемент строго більший за попередній, і яка має найбільшу можливу довжину серед усіх таких підпослідовностей.

Послідовність \(x\) називається підпослідовністю послідовності \(y\), якщо з \(y\) можна видалити деяку кількість елементів (можливо, нульову), щоб залишилась послідовність \(x\).