343. Recycling
0
Hard
As the marketing head of a large multinational corporation, you have created a bar graph for your latest presentation. However, for your next project, you need a rectangular sheet and want to minimize paper waste.
Since the bar graph is no longer needed, 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, your task is 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 in the histogram.
The second line contains N integers, representing the height of each bar in the histogram.
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