题目描述

题目译自 Ukrainian Olympiads in Informatics 2025 Stage 4 Day1 T2. Розбиття на три

在一个圆环上放置了 $n$ 个非负整数 $a_1, a_2, \ldots, a_n$。在圆环上相邻的数字依次为 $a_1$ 与 $a_2$、$a_2$ 与 $a_3$、……、$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$。

数据范围与提示

详细子任务附加限制及分值如下表所示：