시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 1024 MB1911960.000%

문제

Мама подарила маленькой девочке Алёне массив чисел. Девочку заинтересовали непрерывные подмассивы с равными числами на концах. Среди таких подмассивов ненулевой длины Алёна хочет найти подмассив с максимальной суммой. Формально говоря, требуется найти такие $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$ --- искомый подмассив с максимальной суммой.

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

예제 입력 1

5
1 2 1 2 3

예제 출력 1

5
2 4

예제 입력 2

3
-1 -1 -1

예제 출력 2

-1
1 1

예제 입력 3

3
1 2 3

예제 출력 3

3
3 3

노트

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