시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB196076367951.245%

문제

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

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

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

입력

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

출력

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

예제 입력 1

3
7
3
4

예제 출력 1

9

출처

University > 중앙대학교 > 2017 중앙대학교 프로그래밍 경진대회(CPC) B번