В поисках максимальной суммы

Мама подарила маленькой девочке Алёне массив чисел. Девочку заинтересовали непрерывные подмассивы с равными числами на концах. Среди таких подмассивов ненулевой длины Алёна хочет найти подмассив с максимальной суммой. Формально говоря, требуется найти такие $1 \leq l \leq r \leq n$, что $a_l = a_r$ и сумма чисел $a_l + a_{l+1} + \dots + a_r$ максимальна.

В первой строке входных данных находится число $n$ ($1 \leq n \leq 1\,000\,000$) --- количество чисел в массиве $a$.

Во второй строке входных данных находятся $n$ целых чисел $a_1, a_2, \dots, a_n$ ($-10^9 \leq a_i \leq 10^9$).

В первой строке выведите максимальную сумму в подмассиве, удовлетворяющем условию задачи.

Во второй строке выведите 2 целых числа $l$ и $r$, такие что $1 \leq l \leq r \leq n$ и $a_l, a_{l + 1}, \dots, a_r$ --- искомый подмассив с максимальной суммой.

Если существует несколько ответов, выведете любой из них.

Обратите внимание, во втором примере все числа отрицательные, но Алёна всё равно должна выбрать какой-то непустой подмассив.