부분배열 고르기 2

길이가 N(1 <= N <= 100,000)인 1차원 배열 A[1], ..., A[N]이 있다.

1 <= i <= j <= N인 두 정수 i, j를 골라 부분배열 A[i], ..., A[j]를 만들 때, 이 부분배열의 점수는 다음과 같다.

(A[i] + ... + A[j]) * min{A[i], ..., A[j]}

즉, 부분배열의 원소 합에 그 부분배열의 최솟값을 곱한 값이 점수이다.

배열 A가 주어질 때, 가능한 부분배열 중 최대 점수를 구하고 그 점수를 만드는 구간을 출력하는 프로그램을 작성하시오.

첫째 줄에 정수 N이 주어진다.

둘째 줄에는 A[1], ..., A[N]을 나타내는 정수 N개가 주어진다. 각 정수는 0 이상 1,000,000 이하이다.

첫째 줄에 가능한 최대 점수를 출력한다.

둘째 줄에 그 점수를 만드는 구간의 시작 위치 i와 끝 위치 j를 출력한다.