Description

Kiudou always asks questions in the online math forum , and sometimes answers other netizen's questions. He accumulated a good popularity in the forum, so he was lucky to be invited to the 8th MathCon conference.During the break, he strolled through the small shops of souvenirs. One of the items caught his attention. This is a small ribbon with a sequence of numbers, and the ribbon seems to consist of n numbers. He thinks that if the sequence of numbers is $a_0,a_1,...,a_{n-1}$ and at the same time $a_i$ is a 32-bit integer, and what the value of the maximum consecutive sequence is.

Format

Input

Input contains multiple cases.

For each case, the first line inputs an integer $n$, and the second line inputs $n$ integers $a_0,a_1,...,a_{n-1}$. Numbers are separated by spaces. The constraint is $-10^7\leq a_i \leq 10^7,1 \leq n \leq 10^6$,

Output

Print the sum of the maximum consecutive sequence, and the starting index $i$ and ending index $j$ of the sequence. If the maximum consecutive sequence is not unique, printing the smallest two index $i$ and $j$.

If $n$ numbers are all negative, the sum is 0, the starting index $i$ is 0, and the ending index $j$ is the last index of the sequence.

Samples

4
1 -8 2 3

5 2 3

Hint