#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

Largest Histogram Rectangle - Classic Problems | Repovive

CLS59. Largest Histogram Rectangle

2s256 MB

Given bar heights of a histogram, find the largest rectangle area that can be formed using contiguous bars.

Constraints

$1 \le n \le 2 \cdot 10^5$
$0 \le h_i \le 10^9$

Input

\begin{array}{l} n \\ h_1 \quad h_2 \quad \ldots \quad h_n \end{array}

Output

area_{\max}

Samples

Input

6
2 1 5 6 2 3

Explanation

The bars with heights 5 and 6 form a rectangle of height 5 and width 2, area 10.

Output

Input

4
4 4 4 4

Explanation

All four bars can be used together, giving area 16.

Output

Input

5
0 2 0 3 3

Explanation

The best rectangle uses the last two bars with height 3, area 6.

Output

$1 \le n \le 2 \cdot 10^5$
$0 \le h_i \le 10^9$

\begin{array}{l} n \\ h_1 \quad h_2 \quad \ldots \quad h_n \end{array}

area_{\max}