Largest Rectangle Area

You are given an array heights, where heights[i] is the height of a bar of width 1 standing at position i; the bars stand side by side in order.

Return the area of the largest axis-aligned rectangle that fits entirely inside the bars. A rectangle spans some contiguous range of positions and its height cannot exceed any bar in that range, so its area is the range's width times the range's minimum bar height.

Examples

Example 1

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The rectangle of height 5 spanning the two bars [5,6] has area 5 * 2 = 10; no larger rectangle fits.

Example 2

Input: heights = [2,4]
Output: 4
Explanation: The single bar of height 4 gives area 4, beating the height-2 rectangle across both bars.