题目描述

给出数组a的元素a[1],a[2],…,a[n]的值，如果我们取连续且非空的一段，那么这段的和最大是多少？

输入格式

第1行，是一个正整数n,数组a的长度。

第2行，用空格隔开的n个整数，依次是[1],a[2],…,a[n]的值。

输出格式

输出为若干行，每行用1个空格隔开的2个自然数，给出一个满足条件的连续自然数段中的第一个数和最后一个数。

所有输出行按第一个数从小到大的排列，保证至少有一个解。

输入样例 #1

5
-61 -86 -51 -46 81

输出样例 #1

81

输入样例 #2

8
-61 -23 0 -34 60 -8 76 38

输出样例 #2

166

输入样例 #3

6
1 -6 5 -4 2 4

输出样例 #3

7

提示

【说明提示】

取5,-4,2,4可以得到最大的和7。

数据范围与约定

对于60%的数据,n≤100。

对于80%的数据,n≤5000。

对于100%的数据,n≤100000；对1≤i≤n,-10000≤a[i]≤10000。数组a中至少有1个正数