Largest Rectangle in Histogram

You are given a histogram represented by n non-negative integers, where each integer denotes the height of a bar and the width of each bar is 1. Your task is to compute the area of the largest rectangle that can be formed by consecutively adjacent bars.

More formally, given an array h of heights, you need to find the maximum value of $$Area = (j - i + 1) \times \min_{i \le k \le j} h_k$$ where i and j are indices of the bars (with 0-based indexing) such that 0 \le i \le j < n.

This problem can be efficiently solved using a stack-based approach in O(n) time.

inputFormat

The first line contains a single integer n denoting the number of bars in the histogram. The second line contains n space-separated non-negative integers representing the heights of the bars.

outputFormat

Output a single integer representing the area of the largest rectangle in the histogram.

6
2 1 5 6 2 3

10