Informatica Online Judge

  히스토그램 [1704 / 06A8]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 25   Total Tried : 29


The Champion of this Problem (C++) : gs16106 - 0ms / 238byte
My Best Submission (C++) : N/A

[koistudy.net (unkonwn)]

Background

다음과 같이 같은 너비이지만 높이가 다른 히스토그램이 있다.

예를 들어, 왼쪽 그림은 높이가 $2$, $1$, $4$, $5$, $1$, $3$, $3$이고 너비가 $1$인 직사각형으로 이루어진 히스토그램이다.





히스토그램에서 가장 큰 직사각형을 구하는 프로그램을 작성하시오. 단 너비는 1이다.

Input

첫 번째 줄에는 막대의 수 n이 가장 처음으로 주어진다. ($1 ≤ n ≤ 100,000$)
두번째 줄부터 $n$개의 정수 $h_1, ..., h_n$ ($0 ≤ h_i ≤ 1,000,000,000$)가 주어진다. 이 숫자들은 히스토그램에 있는 막대(직사각형)의 높이이며, 왼쪽부터 오른쪽까지 순서대로 주어진다.

Output

히스토그램에서 가장 큰 직사각형의 넓이를 출력한다.

IO Example

입력
7
2 1 4 5 1 3 3

출력
8

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]