Розбиття на три

Вхідні дані

У першому рядку задано одне ціле число $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$.

Оцінювання

1. ($2$ бали): n = 3;

2. ($4$ бали): a_i \le 1 для 1 \le i \le n;

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$ бали): без додаткових обмежень.