The input of the program is a natural number N, and then N integers. It is necessary to determine the maximum sum of adjacent elements of the sequence. N does not exceed 1000000, each element of the sequence does not exceed 100 in absolute value.
Examples
| # |
Input |
Output |
| 1 |
9
-2
1
-3
4
-1
2
1
-5
4
|
6 |
Explanations: for a given sequence of numbers (-2 1 -3 4 -1 2 1 -5 4), the largest sum can be obtained for an adjacent sequence of elements: 4 -1 2 1.
The decision for 2 points is awarded when the program passes 50% of the tests, 3 points - when the program passes 75% of the tests.