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 |
Запрещенные операторы: sort; min; max; reverse; count; sum; index