Феоктист Всеволодович — преподаватель физкультуры старой закалки, глубоко убеждённый, что в начале каждого урока школьников необходимо построить по росту. Для этого он сначала просит школьников построиться самостоятельно, после чего последовательно меняет местами про- извольную пару стоящих рядом учеников, пока шеренга не примет желанный вид.
Всего на урок пришло N детей, изначально построившихся таким образом, что рост стоящего на позиции i равен hi (используется нумерация c 1). Можно считать, что все числа hi различны и лежат в диапазоне от 1 до N. Шеренга считается упорядоченной, если на первой позиции стоит школьник ростом один, на второй позиции стоит школьник ростом два и так далее.
Феоктист Всеволодович получает большое удовольствие от процесса упорядочивания школьни- ков, поэтому он всегда выбирает наиболее длинную последовательность обменов. С другой стороны, он не хочет чтобы ученики догадались о том, что он умышленно затягивает построение, поэтому никогда не делает заведомо бессмысленных обменов. А именно, преподаватель никогда не меняет местами школьников на позициях i и j, если hi < h
j . Очевидно, что данное ограничение делает процесс сортировки шеренги по росту конечным.
Староста Саша очень любит играть в волейбол и прекрасно понимает, что чем дольше препо- даватель будет расставлять всех по местам, тем меньше времени останется для игры. Ученики уже построились некоторым образом, а Феоктист Всеволодович вышел поговорить по телефону, так что Саша может успеть поменять местами ровно двух школьников, необязательно стоящих рядом в ше- ренге. Разумеется, он хочет сделать это таким образом, чтобы преподаватель как можно быстрее закончил упорядочивать шеренгу (Саша давно уже раскусил, как именно действует Феоктист Всево- лодович). С информатикой у старосты всегда были определённые проблемы, поэтому ему требуется ваша помощь.
Формат входных данных
В первой строке ввода содержится единственное число N — количество школьников на уроке (1 <= N <= 1 000 000). Во второй строке записано N различных целых чисел h
i (1 <= h
i <= N). i-е число соответствует росту школьника стоящего на i-й позиции.
Формат выходных данных
Выведите два числа — номера позиций школьников, которым необходимо поменяться местами, чтобы минимизировать количество действий преподавателя. Если таких пар несколько, то выведите любую из них. Если никому меняться местами не нужно, выведите -1 -1.
| Ввод |
Вывод |
5
2 4 3 5 1 |
2 5 |
| 4 1 2 3 4 |
-1 -1 |
10
2 3 7 1 5 10 4 6 9 8 |
3 7 |