Partitioning into Three

Input

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.

Output

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.

Examples

Note

In the third example, the optimal partition looks as follows:

In this case, the sums in the groups are $10$, $11$, and $10$.

Scoring

1. ($2$ points): n = 3;

2. ($4$ points): a_i \le 1 for 1 \le i \le n;

3. ($13$ points): there exists a partition where the sought difference is equal to $0$;

4. ($8$ points): n \le 100;

5. ($9$ points): n \le 2000;

6. ($13$ points): n \le 5000;

7. ($28$ points): n \le 10^5;

8. ($23$ points): with no additional restrictions.