Largest Rectangle in Histogram

Given a histogram where the width of each bar is 1, your task is to find the area of the largest rectangle in the histogram. The histogram is represented by an array of integers where each integer represents the height of a bar. The rectangle must be formed by consecutive bars, and its area is calculated as the minimum height among these bars multiplied by the number of bars.

In mathematical terms, if the histogram is given by an array ( h = [h_1, h_2, \dots, h_n] ), then the area for a rectangle spanning indices ( i ) to ( j ) is given by: [ A = \min_{i \le k \le j} h_k \times (j - i + 1)] Your goal is to compute the maximum such area.

inputFormat

Input is read from standard input. The first line contains a single integer ( n ) representing the number of bars in the histogram. The second line contains ( n ) space-separated integers representing the heights of the bars.

outputFormat

Output to standard output a single integer representing the area of the largest rectangle in the histogram.## sample

6
2 1 5 6 2 3

10