- Time limit: 1.00 s
- Memory limit: 512 MB
Uolevi and Maija are going sledding. They are traveling along a road, seeking the tallest hill to descend. The road is n meters long and the height at i meters from the start of the road is a_i. Help Uolevi and Maija find the tallest hill, i.e. a monotonically increasing or decreasing segment where the height difference between the endpoints is maximized. Find the endpoints L and R of such a segment.
Input
The first line contains a single integer n. The second line contains n integers a_1,\,a_2,\ldots,\,a_n.
Output
Print the endpoints of the segment, L and R. If there are multiple answers, print any.
Constraints
- 2 \leq n \leq 10^5
- 1 \leq a_i \leq 10^9
- a_i \neq a_j if i \neq j
- 1 \leq L < R \leq n
Example 1
Input:
5 1 11 9 19 4
Output:
4 5
Example 2
Input:
10 3 5 17 18 19 20 8 2 1 7
Output:
6 9
Example 3
Input:
3 1 1000000000 2
Output:
1 2