Современный Пеннивайз поспорил со своей версией из фильма 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$$$ несколько, выведите любую из них.
5 5 1 1 1 1
1 1 2
4 1 2 3 4
1 2 4
В первом тесте оптимальным выбором является $$$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$$$.