부분배열 고르기

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

1 <= i <= j <= N을 만족하는 두 인덱스 i, j에 대해, i부터 j까지의 부분배열 점수는

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

으로 정의된다.

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

배열이 주어졌을 때, 연속한 부분배열 중 얻을 수 있는 최대 점수를 구하라.

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

둘째 줄에는 A[1], ..., A[N]을 나타내는 정수들이 주어진다. 각 정수는 음이 아니며 1,000,000을 넘지 않는다.

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

i = 3, j = 5를 선택하면 점수는 (6 + 4 + 5) * 4 = 60이 된다.