题目描述

有 $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}]$。

如果存在多个正确答案，输出任意一个均可。

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

提示

在第三个样例中，最优划分如下：

此时，各组的数字之和分别为 $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 完成