CSES - Aalto Competitive Programming 2024 - wk5 - Wed - Sledding
  • 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