The Perfect StackMedium

The Perfect Stack

Medium+30 XP · +10 Aurastackmonotonic stackhistogram

A group of friends is building a temporary stage for a college festival. The stage is constructed using several wooden planks of varying heights, placed side-by-side. They want to find the largest rectangular area that can be formed by these planks, considering the ground as the base. This area must be fully contained within the planks.

Given the heights of the planks, find the maximum rectangular area they can form.

Input

The first line contains an integer N, the number of planks. The second line contains N space-separated integers, representing the heights of the planks.

Output

Print a single integer, the maximum rectangular area.

Constraints

1 <= N <= 200000 1 <= height[i] <= 10^9

Time limit 1 s (native code; slower languages get more)Memory 256 MB15 hidden tests

Example 1

Input
5
2 1 5 6 2 3
Output
10

The largest rectangle is formed by bars of height 5 and 6, with a minimum height of 5 and width 2, area 10.

Example 2

Input
3
1 2 3
Output
4

The largest rectangle uses all bars with minimum height 1, width 3, area 3.

Hints