Given a histogram with $n$ bars (unit width) and heights $h_0, \dots, h_{n-1}$, compute the maximum rectangle area fully contained in the histogram.

Definition: For any span $[l,r]$ with minimal height $m = \min_{l \le i \le r} h_i$, rectangle area is $(r-l+1) \cdot m$. We want $$ \max_{0 \le l \le r < n} (r-l+1) \cdot \min_{l \le i \le r} h_i. $$

Input Format

n
h_0 h_1 ... h_{n-1}

Output Format

area

Maximum rectangle area.

Example 1

Input

6
2 1 5 6 2 3

Output

10

Example 2

Input

2
2 4

Output

4

Constraints

• $1 \le n \le 10^5$
• $0 \le h_i \le 10^4$

Source: LeetCode & GPT-5. Things might be inaccurate. Contact TAs if you find any problems.