퍼즐 자르기

시간 제한2초메모리 제한256 MB

요약

히스토그램의 각 막대 높이가 주어질 때, 그 안에 들어가는 가장 큰 축에 평행한 직사각형의 넓이를 구한다.

난이도: 보통10점 중 6점
유형: 스택, 배열
정답자: 아직 제출이 없습니다

문제

상렬이에게는 히스토그램 모양의 플라스틱 퍼즐 조각이 많다. 이제 퍼즐이 필요 없어져서 버리려고 했는데, 갑자기 플라스틱 판이 많이 필요해졌다. 그래서 퍼즐에서 직사각형 모양을 잘라내 재활용하기로 했다.

히스토그램은 이를 이루는 직사각형의 높이로 주어진다. 각 직사각형의 너비는 1로 모두 같고, 밑변은 한 직선 위에 나란히 붙어 있다. 잘라낼 직사각형은 변이 축과 나란해야 하며, 퍼즐 안에 완전히 들어가야 한다.

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

입력

첫째 줄에 히스토그램을 이루는 직사각형의 개수 $N$ ( $1 \le N \le 100{,}000$ )이 주어진다. 이어지는 $N$ 개의 줄에 각 직사각형의 높이 $H_i$ ( $1 \le H_i \le 1{,}000{,}000$ )가 왼쪽부터 차례대로 한 줄에 하나씩 주어진다.

출력

잘라낼 수 있는 직사각형의 최대 넓이를 첫째 줄에 출력한다. 답은 32비트 정수 범위를 넘을 수 있다.

예제7

예제 1
입력
```
3
7
3
4
```
예상 출력
```
9
```
예제 2
입력
```
1
1
```
예상 출력
```
1
```
예제 3
입력
```
1
1000000
```
예상 출력
```
1000000
```
예제 4
입력
```
5
1
2
3
4
5
```
예상 출력
```
9
```
예제 5
입력
```
5
5
4
3
2
1
```
예상 출력
```
9
```
예제 6
입력
```
3
2
1
2
```
예상 출력
```
3
```
예제 7
입력
```
7
6
2
5
4
5
1
6
```
예상 출력
```
12
```