최대 합을 찾아서

엄마가 어린 소녀 알료나에게 숫자 배열을 선물했다. 알료나는 양 끝의 수가 같은 연속 부분 배열에 관심을 가졌다. 이런 부분 배열 중 길이가 0이 아닌 것들 가운데 합이 최대인 부분 배열을 찾으려 한다. 형식적으로 말하면, $a_l = a_r$을 만족하면서 합 $a_l + a_{l+1} + \dots + a_r$이 최대가 되는 $1 \leq l \leq r \leq n$을 구해야 한다.

첫 번째 줄에 배열 $a$의 원소 개수 $n$ ($1 \leq n \leq 1000000$)이 주어진다. 두 번째 줄에 정수 $a_1, a_2, \dots, a_n$ ($-10^9 \leq a_i \leq 10^9$)이 주어진다.

첫 번째 줄에 조건을 만족하는 부분 배열의 최대 합을 출력한다. 두 번째 줄에는 그 최대 합을 갖는 부분 배열 $a_l, a_{l+1}, \dots, a_r$을 나타내는 두 정수 $l$과 $r$을 $1 \leq l \leq r \leq n$을 만족하도록 출력한다. 답이 여러 개이면 그중 아무거나 출력해도 된다.

두 번째 예제에서는 모든 수가 음수이지만, 알료나는 그래도 비어 있지 않은 부분 배열을 하나 골라야 한다.