최대 넓이

면접 대비

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

요약

N개 기둥 높이가 주어질 때 빈칸 없이 채울 수 있는 가장 큰 직사각형 넓이를 구합니다.

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

문제

해안가에 호텔을 짓는 사업은 수익이 크다. 그래서 International Ocean Investment는 흑해 연안의 땅을 사들여 최대한 큰 호텔을 지으려고 한다. 여러 사정으로 호텔의 바닥은 직사각형이어야 한다. 회사는 이 땅 위에 그릴 수 있는 직사각형 중 넓이가 가장 큰 것을 찾으려 한다.

땅은 같은 크기의 정사각형으로 이루어진 $N$ 개의 열로 나뉘어 있다(그림에서 흰색 부분). 열에는 왼쪽부터 차례로 $1, 2, \ldots, N$ 의 번호가 붙어 있고, 직사각형은 이 정사각형을 정수 개 모아서 만들어야 한다. 각 열마다 그 열에 온전히 들어 있는 정사각형의 개수를 세었다. 이렇게 만들 수 있는 직사각형의 최대 넓이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 양의 정수 $N$ 이 주어진다( $N \le 1\,000\,000$ ).

둘째 줄에 $N$ 개의 정수 $D_1, D_2, \ldots, D_N$ 이 주어진다. $D_i$ 는 $i$ 번째 열에 있는 정사각형의 개수이고, $0 < D_i \le 15\,000$ 이다.

출력

찾은 최대 넓이를 출력한다. 이 값은 32비트 부호 있는 정수의 범위를 넘을 수 있다.

예제5

예제 1
입력
```
11
6 5 2 7 8 6 8 3 5 6 7
```
예상 출력
```
24
```
예제 2
입력
```
8
2 1 5 6 2 3 1 4
```
예상 출력
```
10
```
예제 3
입력
```
1
15000
```
예상 출력
```
15000
```
예제 4
입력
```
1
1
```
예상 출력
```
1
```
예제 5
입력
```
5
4 4 4 4 4
```
예상 출력
```
20
```