题目描述

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.

输入格式

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.

输出格式

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.

4
1 2 3 4

1
1 3 4

7
1 6 1 0 5 3 2

0
2 3 6

8
3 1 4 1 5 9 2 6

1
3 6 8

提示

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

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

Scoring

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