盛最多水的容器

题目描述

给定一个长度为 n 的非负整数数组 height。

数组中第 i 个元素表示一条垂线，其两个端点分别为 (i, 0) 和 (i, height[i])。

请从中找出两条垂线，使得它们与 x 轴共同构成的容器可以容纳最多的水，并输出这个最大值。

注意：你不能倾斜容器。

输入格式

第一行输入一个整数 n，表示数组长度。

第二行输入 n 个非负整数，表示数组 height。

输出格式

输出一个整数，表示容器可以储存的最大水量。

数据范围

2 <= n <= 10^5

0 <= height[i] <= 10^5

样例 1

输入

9
1 8 6 2 5 4 8 3 7

输出

49

样例 2

输入

2
1 1

输出

1