题目描述

给定一个由 $n$ 个整数组成的数组。记 $sum(l, r)$ 为数组中从位置 $l$ 到位置 $r$ 之间所有数的和（包含第 $l$ 个元素，不包含第 $r$ 个元素）。下标 $l$ 和 $r$ 满足 $0 \le l \le r \le n$。数组下标从 $0$ 开始编号。

例如，若 $a = [-5, 3, 9, 4]$，则 $sum(0, 1) = -5$，$sum(0, 2) = -2$，$sum(1, 4) = 16$，且对于 $0$ 到 $4$ 的每个 $i$，都有 $sum(i, i) = 0$。

请选择三个分隔符的下标 $delim_0, delim_1, delim_2$（$0 \le delim_0 \le delim_1 \le delim_2 \le n$），将数组划分成四段，使得下式的值最大：

注意，某些 $sum(l, r)$ 可能对应空区间（当某个区间的 $l = r$ 时）。

输入

第一行包含一个整数 $n$（$1 \le n \le 5000$）。

第二行包含 $n$ 个整数 $a_0, a_1, \dots, a_{n-1}$（$-10^9 \le a_i \le 10^9$）。

输出

输出三个下标，使得 $res$ 的值最大。如果存在多个答案，输出任意一个即可。

样例

样例 1

输入：

3
-1 2 3

输出：

0 1 3

样例 2

输入：

4
0 0 -1 0

输出：

0 0 0

样例 3

输入：

1
10000

输出：

1 1 1