Мікеланджело замовив піцу пепероні з Antonio’s Pizza-Rama. Піца поділена на шматків.
Шматки піци мають різну гостроту. Шматки піци пронумеровані в порядку за годинниковою стрілкою від 1 до , гострота -го шматка рівна p_i.
Мікеланджело обирає один шматок піци, і, перебираючи шматки піци за годинниковою стрілкою починаючи з цього шматка, записує гостроти всіх шматків піци у блокнот. Далі знаходить найдовшу зростаючу підпослідовність записаних чисел і з’їдає відповідні їм шматки, а інші шматки віддає Леонардо, Рафаелю та Донателло.
Знайдіть два циклічні зсуви піци, для яких Мікеланджело з’їсть різну кількість шматків.
У першому рядку задано ціле число — кількість шматків піци.
У другому рядку задано цілих чисел p_i — гостроти шматків піци в порядку за годинниковою стрілкою.
2 \le n \le 5 \cdot 10^5,
є перестановкою цілих чисел від до .
У першому рядку виведіть цілих чисел — перший циклічний зсув перестановки .
У другому рядку виведіть цілих чисел — другий циклічний зсув перестановки .
Можна показати, що відповідь на задачу завжди існує.
Приклад
Найдовша зростаюча підпослідовність — це підпослідовність елементів масиву, у якій кожен наступний елемент строго більший за попередній, і яка має найбільшу можливу довжину серед усіх таких підпослідовностей.
Послідовність називається підпослідовністю послідовності , якщо з можна видалити деяку кількість елементів (можливо, нульову), щоб залишилась послідовність .