P12545 [UOI 2025] Partitioning into Three

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.

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.