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