Пепероні#12984

Пепероні

2 секунди
512 мегабайтів
Складна

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

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

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

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

Вхідні дані

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

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

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

є перестановкою цілих чисел від до .

Вихідні дані

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

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

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

Приклади

Приклад

Loading
Loading

Примітка

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

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