Контейнер с наибольшим количеством воды

Лимит времени 1 секунда

Лимит использования памяти 128 MiB

Задан массив целых чисел height длины n. Имеются n вертикальных линий, конечными точками i-ой линии являются (i, 0) и (i, height[i]).

Найдите две линии, которые вместе с осью x образуют контейнер, содержащий наибольшее количество воды.

Входные данные

Первая строка содержит размер n (n ≤ 10^5) массива height. Вторая строка содержит n натуральных чисел — элементы массива height, не больших 10^9.

Выведите максимальное количество воды, которое может хранить контейнер.

Входные данные #1

9
1 8 6 2 5 4 8 3 7

Выходные данные #1