題目描述

給定一個由非負整數組成的直方圖，每個柱子的寬度為1，求出直方圖中能夠圍成的最大矩形的面積。 

輸入：第一行是一個正整數n，表示柱子的個數。接下來一行有n個非負整數，表示每個柱子的高度。 輸出：一個正整數，表示最大矩形的面積。 限制：1 <= n <= 100000，0 <= 柱子高度 <= 100000 範例： 輸入： 6 2 1 5 6 2 3 輸出： 10

解釋： 最大矩形是由第三個和第四個柱子圍成的，面積為5*2=10。

輸入格式

第一行是一個正整數n，表示柱子的個數。接下來一行有n個非負整數，表示每個柱子的高度。

輸出格式

一個正整數，表示最大矩形的面積。

限制：1 <= n <= 100000，0 <= 柱子高度 <= 100000 

Samples

6
2 1 5 6 2 3

10

原始資料

• Zero1 題號：b049
• Hydro 題號：Z1049
• Locale：zh_TW
• Display：open