Как вы знаете, девочка Даша постоянно что-то ищет. На этот раз ей дали перестановку, и она хочет найти такой её подотрезок, что ни один из элементов на его концах не является ни минимумом, ни максимумом всего подотрезка. Более формально, вас просят найти такие числа \(l\) и \(r\) \((1 \leq l \leq r \leq 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\) присутствует в массиве).
Помогите Даше найти такой подотрезок, либо скажите, что такого подотрезка не существует.
Выходные данные
Для каждого набора входных данных выведите \(-1\), если искомого подотрезка не существует.
Иначе, выведите два индекса \(l, r\), такие что \([a_{l}, a_{l + 1}, \ldots, a_{r}]\) удовлетворяет всем условиям.
Если существует несколько решений, то выведите любое из них.
Примечание
В первом и четвертом наборе входных данных можно показать, что искомых отрезков нет.
Во втором наборе входных данных подотрезок \([1, 4]\) удовлетворяет всем условиям, потому что \(\max(a_1, a_2, a_3, a_4) = 4, \min(a_1, a_2, a_3, a_4) = 1\), и как мы видим, все условия выполняются .
В третьем наборе входных данных подотрезок \([2, 6]\) также удовлетворяет всем описанным условиям.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3
1 2 3
4
2 1 4 3
7
1 3 2 4 6 5 7
6
2 3 6 5 4 1
|
-1
1 4
2 6
-1
|