该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

给定一个长度为 $n$ 的整数数组 $a$. 有 n 条垂线，第 i 条线的两个端点是 $(i, 0)$ 和 $(i, a[i])$, 找出其中的两条垂线, 使得它们与 x 轴共同构成的容器可以容纳最多的水.

Format

Input

第一行包含一个整数 $n$ $(2 \leq n \leq 10^5)$, 代表数组的长度.

第二行包含 $n$ 个整数, 代表垂线的高度$(0 \leq a[i] \leq 10^4)$.

Output

输出一个整数代表能容纳最多的水.

Samples

9
1 8 6 2 5 4 8 3 7

49

Limitation

1s, 1024KiB for each test case.