There are $n$ non-negative integers $a_1, a_2, \ldots, a_n$ arranged in a circle. The neighboring numbers in the circular order are $a_1$ and $a_2$, $a_2$ and $a_3$, $\ldots$, $a_{n-1}$ and $a_n$, $a_n$ and $a_1$.

Partition these numbers into three non-empty groups such that each number belongs to exactly one group, the numbers in each group are consecutively arranged in a circle, and the difference between the maximum and minimum sums of the numbers in the groups is minimized.

Input

The first line contains one integer $n$ $(3 \le n \le 10^6)$ -- the number of arranged numbers.

The second line contains $n$ non-negative integers $a_1, a_2, \ldots, a_n$ $(0 \le a_i \le 10^9)$ -- the numbers arranged in a circle.

Output

In the first line, output one integer -- the difference between the maximum and minimum sums of the numbers in the groups in the optimal partition.

In the second line, output three integers $x$, $y$, $z$ $(1 \le x < y < z \le n)$~--- such indices that the optimal partition of the numbers into three groups is of the form $[a_{x}, a_{x+1}, \ldots, a_{y-1}]$, $[a_{y}, a_{y+1}, \ldots, a_{z-1}]$, $[a_{z}, a_{z+1}, \ldots, a_{n-1}, a_{n}, a_{1}, a_{2}, \ldots, a_{x-1}]$.

If there are multiple correct answers, any of them is allowed to be output.

Example

Input

4
1 2 3 4

Output

1
1 3 4

Input

7
1 6 1 0 5 3 2

Output

0
2 3 6

Input

8
3 1 4 1 5 9 2 6

Output

1
3 6 8

Notes

In the third example, the optimal partition looks as follows:

In this case, the sums in the groups are $10$, $11$, and $10$.

Scoring

1. ($2$ points): $n = 3$;
2. ($4$ points): $a_i \le 1$ for $1 \le i \le n$;
3. ($13$ points): there exists a partition where the sought difference is equal to $0$;
4. ($8$ points): $n \le 100$;
5. ($9$ points): $n \le 2000$;
6. ($13$ points): $n \le 5000$;
7. ($28$ points): $n \le 10^5$;
8. ($23$ points): with no additional restrictions.