The Perfect Stack
A group of friends is building a temporary stage for a college festival. The stage is constructed using several wooden planks of varying heights, placed side-by-side. They want to find the largest rectangular area that can be formed by these planks, considering the ground as the base. This area must be fully contained within the planks.
Given the heights of the planks, find the maximum rectangular area they can form.
Input
The first line contains an integer N, the number of planks. The second line contains N space-separated integers, representing the heights of the planks.
Output
Print a single integer, the maximum rectangular area.
Constraints
1 <= N <= 200000 1 <= height[i] <= 10^9
Example 1
5 2 1 5 6 2 3
10
The largest rectangle is formed by bars of height 5 and 6, with a minimum height of 5 and width 2, area 10.
Example 2
3 1 2 3
4
The largest rectangle uses all bars with minimum height 1, width 3, area 3.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 2 1 5 6 2 3
3 1 2 3