일렬로 놓인 N개의 칸이 있고, 각 칸에는 하나의 정수가 적혀 있다.

왼쪽부터 차례대로 적힌 수를 A[1], A[2], ..., A[N]이라고 하자.

이 칸들 중에서 연속한 구간 하나를 정해 값을 계산하려고 한다.

구간의 시작을 i, 끝을 j라고 할 때, 단 1 ≤ i ≤ j ≤ N이어야 한다.

선택한 구간의 값은 다음과 같이 정한다.

• 먼저 A[i]부터 A[j]까지의 수를 모두 더한다.

• 그리고 그 구간 안에 들어 있는 수들 중 가장 작은 값을 찾는다.

• 위 두 값을 곱한 것이 해당 구간의 점수가 된다.

즉, 구간 [i, j]의 점수는 다음과 같다.

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

주어진 수열에서 가능한 모든 연속한 구간 중 점수가 가장 큰 경우를 찾아, 그 점수를 출력하는 프로그램을 작성하시오.

입력

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

다음 줄에는 A[1], A[2], ..., A[N]을 나타내는 정수들이 주어진다.

각각의 정수는 음이 아닌 값을 가지며, 1,000,000을 넘지 않는다.

출력

첫째 줄에 얻을 수 있는 점수의 최댓값을 출력한다.

제한

• 1 ≤ N ≤ 100,000

예제 입력 1

6
3 1 6 4 5 2

예제 출력 1

60

힌트

i = 3, j = 5로 고르면 점수는 다음과 같이 계산된다.

(6 + 4 + 5) × 4 = 60