P12545 [UOI 2025] Partitioning into Three

有 $n$ 个**非负**整数 $a_1, a_2, \ldots, a_n$ 排成一个环形。环形顺序中相邻的数字为 $a_1$ 和 $a_2$，$a_2$ 和 $a_3$，$\ldots$，$a_{n-1}$ 和 $a_n$，$a_n$ 和 $a_1$。 将这些数字分成三个**非空**的组，使得每个数字恰好属于一个组，每组中的数字在环形排列中是**连续的**，并且各组数字之和的最大值与最小值之差最小。

第一行包含一个整数 $n$ $(3 \le n \le 10^6)$ —— 排列的数字个数。 第二行包含 $n$ 个非负整数 $a_1, a_2, \ldots, a_n$ $(0 \le a_i \le 10^9)$ —— 环形排列的数字。

第一行输出一个整数 —— 最优划分下各组数字之和的最大值与最小值之差。 第二行输出三个整数 $x$, $y$, $z$ $(1 \le x < y < z \le n)$ —— 表示最优划分的三个组的边界索引，其中： - 第一组为 $[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}]$。 如果存在多个正确答案，输出任意一个均可。

在第三个样例中，最优划分如下：  此时，各组的数字之和分别为 $10$、$11$ 和 $10$。 ### 评分标准 - （$2$ 分）：$n = 3$； - （$4$ 分）：对于所有 $1 \le i \le n$，$a_i \le 1$； - （$13$ 分）：存在一种划分使得所求差值为 $0$； - （$8$ 分）：$n \le 100$； - （$9$ 分）：$n \le 2000$； - （$13$ 分）：$n \le 5000$； - （$28$ 分）：$n \le 10^5$； - （$23$ 分）：无额外限制。 翻译由 DeepSeek V3 完成