히스토그램은 여러 개의 막대가 일정한 간격으로 나열된 막대그래프이다.

각 막대의 폭은 모두 같으며, 막대의 높이는 정수로 주어진다.

예를 들어, 어떤 히스토그램의 높이가 왼쪽부터 차례대로

2 1 4 5 1 3 3

과 같이 주어질 수 있다.

이제 주어진 히스토그램 안에 직사각형 하나를 그리려고 한다.

이때 직사각형은 히스토그램의 막대들이 차지하는 영역 안에 완전히 포함되어야 하며, 직사각형의 밑변은 항상 히스토그램의 아랫변과 평행해야 한다.

하나의 직사각형은 연속된 몇 개의 막대에 걸쳐 그릴 수 있다.

이 경우 직사각형의 높이는 선택한 막대들 중 가장 낮은 막대의 높이를 넘을 수 없다.

주어진 히스토그램에서 만들 수 있는 직사각형 중 넓이가 가장 큰 것의 넓이를 구하는 프로그램을 작성하시오.

입력

첫 행에는 N이 주어진다.
N은 히스토그램의 가로 칸의 수이다.

다음 N행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다.

각 칸의 높이는 1,000,000,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 가장 큰 직사각형의 넓이를 출력한다.
이 값은 20억을 넘지 않는다.

제한

• 1 ≤ N ≤ 100,000

예제 입력 1

7
2
1
4
5
1
3
3

예제 출력 1

8