← 返回题目列表

Codeforces · 846/C

C. 四段

中文机器翻译题面 查看原题

给定一个由 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