给定一个由 n 个整数组成的数组。令 sum(l, r) 为从 l 到 r 不包含的位置上的所有数字的总和(第 l 个元素被计算在内,第 r 个元素未被计算在内)。对于索引 l 和 r,满足 0 ≤ l ≤ r ≤ n。数组中的索引从0开始编号。
例如,如果 a = [ - 5, 3, 9, 4],则对于从 0 到 4 的每个 i,sum(0, 1) = - 5、sum(0, 2) = - 2、sum(1, 4) = 16 且 sum(i, i) = 0。
选择三个分隔符 delim0、delim1、delim2 的索引 (0 ≤ delim0 ≤ delim1 ≤ delim2 ≤ n) 并以这样的方式划分数组,使 res = sum(0, delim0) - sum(delim0, delim1) + sum(delim1, delim2) - sum(delim2, n) 的值最大。
请注意,某些表达式 sum(l, r) 可以对应于空段(如果某些段的 l = r)。
输入
第一行包含一个整数 n (1 ≤ n ≤ 5000)。
第二行包含 n 个数字 a0, a1, ..., an - 1 (- 109 ≤ ai ≤ 109)。
输出
选择三个索引,使 res 的值最大。如果有多个答案,请打印其中任何一个。
示例
输入 #1
3 -1 2 3
输出 #1
0 1 3
输入 #2
4 0 0 -1 0
输出 #2
0 0 0
输入 #3
1 10000
输出 #3
1 1 1