736. Recycling
0
Hard
As the marketing head of a large multinational corporation, you have created a bar graph for your latest presentation. Now, for your next project, you need a rectangular sheet. However, you want to minimize paper waste.
Since you no longer need the bar graph, you can repurpose the sheets from it. Given an array of integers representing the heights of the bars in the histogram, where each bar has a width of 1, you need to determine the area of the largest rectangle that can be formed in the histogram.
Input Format
The first line of input contains an integer N, representing the number of bars in the histogram.
The second line contains N integers, representing the height of each bar respectively.
The second line contains N integers, representing the height of each bar respectively.
Output Format
Print the largest area of the rectangle that can be formed in the histogram.
Example
Input
6
2 1 5 6 2 3
Output
10
Constraints
Constraints:
1<=N<=10^5
0<=height[i]<=10^4
0<=height[i]<=10^4
Loading...
View Submissions
Console