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$.