Largest Rectangle

Skyline Real Estate Developers is planning to demolish a number of old, unoccupied buildings and construct a shopping mall in their place. Your task is to find the largest solid area in which the mall can be constructed.

There are a number of buildings in a certain two-dimensional landscape. Each building has a height, given by . If you join  adjacent buildings, they will form a solid rectangle of area .

For example, the heights array . A rectangle of height  and length  can be constructed within the boundaries. The area formed is .

Function Description

Complete the function largestRectangle int the editor below. It should return an integer representing the largest rectangle that can be formed within the bounds of consecutive buildings.

largestRectangle has the following parameter(s):

• h: an array of integers representing building heights

Input Format

The first line contains , the number of buildings. 
The second line contains  space-separated integers, each representing the height of a building.

Constraints

Output Format

Print a long integer representing the maximum area of rectangle formed.

Sample Input

5
1 2 3 4 5

Sample Output

9

Explanation

An illustration of the test case follows. 

---

이 문제는 자칫 위의 예제만 보고서 sort 후에 최대 면적을 계산하면 되지 않을까 싶지만, 문제는 sort 없이 왼쪽과 오른쪽의 연속된 별딩 면적을 계산해야 한다.

Sort를 하게 되면 잘못된 결과가 나오게 된다. 중간에 작은 숫자가 포함되어 있는데, sort를 하게 되면 이런 것들이 제거되므로...

다만.....

왜 이 문제에서 굳이 Stack 또는 Queue를 사용할 필요가 있느냐 이다..카테고리가 stack and queue라서.....

Count를 이용하지 않고 Stack에 조건에 맞는 값들을 넣어둔 후, stack의 갯수로 Max값을 처리할 수는 있지만, 굳이 그럴 필요가 없다.

그냥 알고리즘 문제가 맞는것 같다.