Given an array of arbitrary integers. Write a program that in one pass through the array finds a continuous piece, the sum of the numbers in which is maximum.
Note. In fact, it is required to find i and j (i<=j) such that the sum of all array elements from a_{i< /sub>} up to and including a_{j} will be the maximum.

Input
The first line is a natural number n <= 100000 — the number of elements in the array. The following n lines define the actual elements of the — integers, modulo not exceeding 30,000.

Imprint
Output a pair of desired index values. If there are several such pairs, then j should be the minimum possible, and if j are equal, the value of i should be the maximum possible. On the first line print i, on the second - j.

Examples

#

Input

Output

1

5
-1
2
3
-2
2

2
3

2

7
2
-2
3
-1
5
-2
7

3
7

Запрещенные операторы: sort; min; max; reverse; count; sum; index