Description

给定 $n$ 个非负整数 $a_1,a_2,\cdots,a_n$，每个数代表坐标中的一个点 $(i, a_i)$ 。在坐标内画 $n$ 条垂直线，垂直线 $i$ 的两个端点分别为 $(i, a_i)$ 和 $(i, 0)$。找出其中的两条线，使得它们与 $x$ 轴共同构成的容器可以容纳最少的水，但是题目保证 $n$ 是一个奇数，并且找出的两条线只能位于中点 $\frac{n+1}{2}$ 的左右两侧。

图中垂直线代表输入n=9,数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最小值为 4（2x2）。你可以在线性时间内解决这个问题吗？

Input Format

第一行一个整数n，表示垂直线的个数。(1 ≤ n ≤ 50000)。

第二行，n个整数，表示垂直线的长度。(垂直线长度 $\le 10^3$)。

Output Format

容纳最少的水量。

9
1 8 6 2 5 4 8 3 7​

4​

Source

贪心 双指针