Даша и поиски
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Как вы знаете, девочка Даша постоянно что-то ищет. На этот раз ей дали перестановку, и она хочет найти такой её подотрезок, что ни один из элементов на его концах не является ни минимумом, ни максимумом всего подотрезка. Более формально, вас просят найти такие числа $$$l$$$ и $$$r$$$ $$$(1 \leqslant l \leqslant r \leqslant n)$$$, что $$$a_l \neq \min(a_l, a_{l + 1}, \ldots, a_r)$$$, $$$a_l \neq \max(a_l, a_{l + 1}, \ldots, a_r)$$$ и $$$a_r \neq \min(a_l, a_{l + 1}, \ldots, a_r)$$$, $$$a_r \neq \max(a_l, a_{l + 1}, \ldots, a_r)$$$.

Напомнима, что перестановкой длины $$$n$$$ называется массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$, выписанных в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ является перестановкой, но $$$[1,2,2]$$$ не является перестановкой ($$$2$$$ встречается дважды в массиве) и $$$[1,3,4]$$$ тоже не является перестановкой ($$$n=3$$$, но $$$4$$$ присутствует в массиве, а $$$2$$$ отсутствует).

Помогите Даше найти такой подотрезок, либо скажите, что такого подотрезка не существует.

Входные данные

В первой строке входных данных вам дано одно целое число $$$n$$$ ($$$1 \leqslant n \leqslant 200\,000$$$) — размер перестановки.

Во второй строке входных данных вам дано $$$n$$$ целых чисел $$$a_1, a_2, \ldots a_n$$$ ($$$1 \leqslant a_i \leqslant n$$$) — элементы перестановки.

Выходные данные

Если искомого подотрезка не существует, выведите $$$-1$$$.

Иначе выведите такие два числа $$$l$$$ и $$$r$$$ $$$(1 \leqslant l \leqslant r \leqslant n)$$$, что $$$[a_l, a_{l + 1}, \ldots, a_r]$$$ удовлетворяет условиям задачи.

Если искомых подотрезков несколько, выведите любой из них.

Примеры

Входные данные
3
1 2 3
Выходные данные
-1
Входные данные
4
2 1 4 3
Выходные данные
1 4

Система оценки

В данной задаче $$$24$$$ теста, помимо тестов из условия. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования.

Решения, корректно работающие при $$$n \leqslant 500$$$, будут набирать не менее $$$30$$$ баллов.

Решения, корректно работающие при $$$n \leqslant 3000$$$, будут набирать не менее $$$51$$$ балла.

Решения, корректно работающие только для случая, когда искомого подотрезка не существует, оцениваются в $$$0$$$ баллов.