시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 492 114 101 42.259%

문제

상렬이에게는 히스토그램 모양의 플라스틱 퍼즐 조각이 많이 있다. 상렬이는 이 퍼즐 조각들이 필요가 없어져 버릴 계획이다. 하지만 갑자기 플라스틱 판이 많이 필요해져 퍼즐에서 직사각형 모양을 잘라내 재활용하려고 한다.

퍼즐의 모양이 주어질 때 자를 수 있는 가장 큰 직사각형의 넓이를 구하는 프로그램을 작성하라.

히스토그램의 정보는 히스토그램을 구성하는 직사각형들의 높이로 주어진다. 각 직사각형의 너비는 1로 모두 같다.

입력

히스토그램을 구성하는 직사각형의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 이어 N개의 줄에 걸쳐 각 직사각형의 높이인 정수 Hi(1 ≤ Hi ≤ 1,000,000)가 주어진다.

출력

잘라낼 수 있는 직사각형의 최대 넓이를 출력하라.

예제 입력 1

3
7
3
4

예제 출력 1

9

힌트