Problem

10 /12


Sum of numbers in an array

Problem

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 ai< /sub> up to and including aj 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