题目描述

有n个非负整数a[1]，a[2]，...，a[n]，每个数代表坐标中的一个点(i, a[i])。在坐标内画n条垂直线，垂直线i的两个端点分别为(i, a[i])和(i, 0)。找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。不能倾斜容器。

输入格式

第一行一个正整数n，表示垂直线的个数(2≤n≤100)；

第二行内输入n个正整数，表示a[i]，不超过int类型表示范围。

输出格式

容器能够容纳水的最大值。

输入/输出样例

9
1 8 6 2 5 4 8 3 7

49

样例解释

图中垂直线代表输入数组{1,8,6,2,5,4,8,3,7}。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

说明/提示

时间1000ms，内存256MiB