| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 16 | 10 | 8 | 66.667% |
Мама подарила маленькой девочке Алёне массив чисел. Девочку заинтересовали непрерывные подмассивы с равными числами на концах. Среди таких подмассивов ненулевой длины Алёна хочет найти подмассив с максимальной суммой. Формально говоря, требуется найти такие 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$ --- искомый подмассив с максимальной суммой.
Если существует несколько ответов, выведете любой из них.
5 1 2 1 2 3
5 2 4
3 -1 -1 -1
-1 1 1
3 1 2 3
3 3 3
Обратите внимание, во втором примере все числа отрицательные, но Алёна всё равно должна выбрать какой-то непустой подмассив.