Как вы знаете, девочка Даша постоянно что-то ищет. На этот раз ей дали перестановку, и она хочет найти такой её подотрезок, что ни один из элементов на его концах не является ни минимумом, ни максимумом всего подотрезка. Более формально, вас просят найти такие числа $$$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]$$$ удовлетворяет условиям задачи.
Если искомых подотрезков несколько, выведите любой из них.
31 2 3
-1
42 1 4 3
1 4
В данной задаче $$$24$$$ теста, помимо тестов из условия. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования.
Решения, корректно работающие при $$$n \leqslant 500$$$, будут набирать не менее $$$30$$$ баллов.
Решения, корректно работающие при $$$n \leqslant 3000$$$, будут набирать не менее $$$51$$$ балла.
Решения, корректно работающие только для случая, когда искомого подотрезка не существует, оцениваются в $$$0$$$ баллов.