28719번 - Они 스페셜 저지다국어

문제

Современный Пеннивайз поспорил со своей версией из фильма 1990-го года, кто из них сможет напугать больше детей. Однако, поскольку Они по-сути являются одним и тем же существом, Они очень не хотят расстраивать друг друга большим перевесом в результатах, и истинной целью их соревнования будет получить результаты, наиболее близкие друг к другу.

Для соревнования был выбран прямой участок канализации, на котором во всех целых точках от 1ドル$ до $n$ прячутся перепуганные дети: в точке с координатой $i$ прячется $a_i$ детей. Старый Пеннивайз пробежит от точки 1ドル$ до точки $l$ включительно, пугая всех детей, встреченных по пути (1ドル \le l$), современный же пробежит от точки $n$ до точки $r$ включительно, делая то же самое ($r \le n$). При чем, так как нет смысла пугать одних и тех же детей дважды, $l < r$.

Обозначим за $S_1$ и $S_2$ количество детей, которых напугают старый и современный Пеннивайзы, соответственно. Помогите Пеннивайзам выбрать $l$ и $r,ドル при которых Они будут иметь наиболее близкие друг к другу количества напуганных детей, то есть при которых достигается минимум $|S_1 - S_2|$.

입력

В первой строке дано одно целое число $n$ --- длина участка канализации (2ドル \leq n \leq 10^6$). В следующей строке даны $n$ целых чисел $a_i$ --- количество детей в $i$-й точке участка (1ドル \leq a_i \leq 10^9$).

출력

В единственной строке выведите три целых числа --- минимальное значение $|S_1 - S_2|,ドル и значения $l$ и $r,ドル при которых это значение достигается. Если различных подходящих пар $l$ и $r$ несколько, выведите любую из них.

제한

노트

В первом тесте оптимальным выбором является $l = 1$ и $r = 2,ドル тогда $S_1 = 5,ドル $S_2 = 4,ドル а $|S_1 - S_2| = 1$.

Во втором тесте оптимальным выбором является $l = 2$ и $r = 4,ドル тогда $S_1 = 3,ドル $S_2 = 4,ドル а $|S_1 - S_2| = 1$.