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