Feoktist Vsevolodovich — a physical education teacher of the old school, deeply convinced that at the beginning of each lesson, schoolchildren must be built according to their height. To do this, he first asks the schoolchildren to line up on their own, after which he sequentially changes places of an arbitrary pair of students standing next to each other until the line takes the desired form.
In total, N children came to the lesson, initially lined up in such a way that the height of the person in position i is equal to hi (numbering c 1 is used). We can assume that all numbers hi are different and lie in the range from 1 to N. A line is considered ordered if the first position is occupied by a student of height one, the second position is occupied by a student of height two, and so on.
Feoktist Vsevolodovich takes great pleasure in the process of ordering schoolchildren, so he always chooses the longest sequence of exchanges. On the other hand, he does not want the students to guess that he is deliberately delaying the formation, so he never makes deliberately meaningless exchanges. Namely, the teacher never swaps students in positions i and j if hi < h
j . Obviously, this restriction makes the process of sorting the rank by height finite.
Headman Sasha loves to play volleyball very much and understands perfectly well that the longer the teacher puts everyone in their places, the less time will be left for the game. The students had already lined up in some way, and Feoktist Vsevolodovich went out to talk on the phone, so that Sasha could have time to change places of exactly two schoolchildren, not necessarily standing side by side in a line. Of course, he wants to do it in such a way that the teacher finishes arranging the line as quickly as possible (Sasha has long figured out exactly how Feoktist Vsevolodovich works). The headman has always had certain problems with computer science, so he needs your help.
Input data format
The first line of input contains the single number N — the number of students in the lesson (1 <= N <= 1,000,000). The second line contains N distinct integers h
i (1 <= h
i <= N). The i-th number corresponds to the height of the student in the i-th position.
Output data format
Print two numbers — position numbers of schoolchildren who need to change places in order to minimize the number of teacher actions. If there are several such pairs, then print any of them. If no one needs to switch places, print -1 -1.
|
Enter |
Output |
5
2 4 3 5 1
|
25 |
|
4 1 2 3 4
|
-1 -1 |
10
2 3 7 1 5 10 4 6 9 8
|
37 |