单子序列最大和

【题目描述】

给一串整数 $a [1… n ]$ ，求出它和最大的子序列，即找出 $1\leq i \leq j \leq n$ ，使 $a [ i ]+ a [ i +1]+…+ a [ j-1 ]+ a [ j ]$ 最大。

【输入格式】

文件的第一行为一个正整数$n$;

第二行有$n$个整数，$-32768 ≤ a[i] ≤ 32767$;

【输出格式】

输出文件第一行有一个整数$i$，表示子序列的起始位置编号。

第二行有一个整数$j$，表示子序列的终止位置编号。

第三行有一个数，是子序列的和。

注：若有多个解，只输出$i$值最小的解，若多个解$i$值相同，则输出$j$值最小的解。

【样例输入】

5
-2 2 5 -1 6

【样例输出】

2
5
12

【数据规模】

对于$30$%的数据,$n\leq100$;

对于$60$%的数据,$n\leq 400$;

对于$100$%的数据,$n\leq 1,000,000$;