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

评分

1.（$2$ 分）：$n = 3$；

2.（$4$ 分）：对所有 $1 \le i \le n$ 有 $a_i \le 1$；

3.（$13$ 分）：存在一个划分使得差值为 $0$；

4.（$8$ 分）：$n \le 100$；

5.（$9$ 分）：$n \le 2000$；

6.（$13$ 分）：$n \le 5000$；

7.（$28$ 分）：$n \le 10^5$；

8.（$23$ 分）：无其他额外限制。