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