| 히스토그램 |
|---|
히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.
히스토그램에서 가장 큰 직사각형을 구하는 프로그램을 작성하시오. (단, 비스듬하거나 경사가 있는 직사각형은 제외한다.) |
| 입력 | |
|---|---|
입력은 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 둘째 줄부터는 n개의 정수 h1, h2, ... , hn (0 ≤ hi ≤ 1000000000)가 주어진다. 이 숫자들은 히스토그램에 있는 직사각형의 높이이며, 왼쪽부터 오른쪽까지 순서대로 주어진다. 모든 직사각형의 너비는 1이다. | |
| 출력 | |
|---|---|
히스토그램에서 가장 큰 직사각형의 넓이를 출력한다. | |
| 예시 | |||
|---|---|---|---|
| 1 | 입력 | 7 2 1 4 5 1 3 3 | |
| 출력 | 8 | ||