To replenish the budget in the country of Avalon, known for its mountainous tourist routes, a new tax for tourists has been introduced. Tax amount
proportional to the length of the route, but since the route passes through the mountains and the distance traveled, depending on the height of the descent and ascent, is difficult to calculate, the tax is calculated without
altitude, that is, the amount of tax is proportional to the horizontal movement made by the tourist group. In addition, by virtue of an old custom, all
tourist groups must move through the mountains of Avalon strictly from west to east. A travel agency wants to save on tax, so they want to develop a tourist
the route with the minimum tax. At the same time, since the route is mountainous, it must contain an ascent uphill and a descent from the mountain, that is, there must be a point on the route,
which is strictly above the beginning and end of the route.
The travel agency compiled a map of the mountains of Avalon, containing information about the height of the mountains when moving from west to east. Mountain heights are measured at points at equal distances.
On this map of the mountains of Avalon, find the minimum length tourist route that satisfies the condition of the ascent and descent.
The first line of the input contains the number N – the number of points on the Avalon mountains map. The next N lines contain information about the height of the mountains at the given N points when moving from west to east. All numbers are natural, not exceeding 10
5.
The program should output two numbers – route start point number and route end point number. The waypoints are numbered from 1 to N. If a route that satisfies
conditions does not exist, the program should print a single number 0.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
7
18
10
15
20
20
10
3 |
3
6 |
Given 7 points with heights 18, 10, 15, 20, 20, 10, 3. The shortest route containing climb and
descent, – it's 15, 20, 20, 10. It starts at point number 3 and ends at point number 6.
|
| 2 |
3
9
8
5 |
0 |
The height of the mountains decreases monotonically, so the required route does not exist. |