题目：

You are given an array of n integer numbers. Let sum(l, r) be the sum of all numbers on positions from l to r non-inclusive (l-th element is counted, r-th element is not counted). For indices l and r holds 0 ≤ l ≤ r ≤ n. Indices in array are numbered from 0.

For example, if a = [ - 5, 3, 9, 4], then sum(0, 1) =  - 5, sum(0, 2) =  - 2, sum(1, 4) = 16 and sum(i, i) = 0 for each i from 0 to 4.

Choose the indices of three delimiters delim0, delim1, delim2 (0 ≤ delim0 ≤ delim1 ≤ delim2 ≤ n) and divide the array in such a way that the value of res = sum(0, delim0) - sum(delim0, delim1) + sum(delim1, delim2) - sum(delim2, n) is maximal.

Note that some of the expressions sum(l, r) can correspond to empty segments (if l = r for some segment).

Input

The first line contains one integer number n (1 ≤ n ≤ 5000).

The second line contains n numbers a0, a1, ..., an - 1 ( - 109 ≤ ai ≤ 109).

Output

Choose three indices so that the value of res is maximal. If there are multiple answers, print any of them.

Examples

input

3
-1 2 3

output

0 1 3

input

4
0 0 -1 0

output

0 0 0

input

1
10000

output

1 1 1

题意：

  给你一个序列，定义一种运算$sum(a,b)=num[a]+…+num[b-1]$，注意$sum(a,a)=0$。让你求出最大的$res=sum(0, delim_0) - sum(delim_0, delim_1) + sum(delim_1, delim_2) - sum(delim_2, n)$时的$delim0，delim1，delim2$。

思路：

  用前缀和去节省每一次求区间和的时间，因为当a，b相同时sum操作是为0的，所以最不理想的时候res中减操作的时候就为0。所以我们就可以去枚举delim0以及delim2，那delim1的话就是在过程中求出一个区间和为最下的非正数的范围就好了。然后每次记录与之前进行比较，取最大值得时候的delim0，delim1，delim2。

实现：

#include <bits/stdc++.h>
using namespace std;
long long sum[int(5e3)+7], num, ans, minn, tmp;
long long calc(int l, int r) {return sum[r]-sum[l];}
int main() {
    int n, a, b, c, pos; while(ans = -0x3f3f3f3f, ~scanf("%d", &n)) {
        for(int i=1 ; i<=n ; i++) scanf("%lld", &num), sum[i] = sum[i-1] + num;
        for(int i=0 ; i<=n ; i++) {
            pos = i, minn = sum[i];
            for(int j=i ; j<=n ; j++) {
                if(sum[j] < minn) pos = j, minn = sum[j];
                tmp = calc(0, i)-calc(i, pos)+calc(pos, j)-calc(j, n);
                if(tmp > ans) a = i, b = pos, c = j, ans = tmp;
            }
        } printf("%d %d %d\n", a, b, c);
    } return 0;
}