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 \lt y \lt 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.
- ($$$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.
41 2 3 4
1 1 3 4
71 6 1 0 5 3 2
0 2 3 6
83 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$$$.
