Container with the most water

Problem

Vertical walls stand along a line, each with a height. Choose two walls. The water held between them has width equal to the distance between the walls and height equal to the shorter wall. Print the largest amount of water.

Input, output and limits

Input: One line of wall heights separated by spaces.
Output: One integer: the largest water amount.
Constraints: 2 ≤ number of walls ≤ 100000
0 ≤ each height ≤ 10000

Examples

Example

Input

1 8 6 2 5 4 8 3 7

Output

Walls of height 8 and 7 are 7 apart: 7 * 7 = 49.

Hints

Try the problem first. Open one hint at a time.

Hint 1

Start with the widest pair of walls.

Hint 2

Move the pointer at the shorter wall, because a shorter wall cannot give more water with a smaller width.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

Merge two sorted listseasy
Pairs under a limitmedium
Sorted squareseasy
Closest pair of costsmedium
Unique values of a sorted listeasy

All Python problems

Problem

Input, output and limits

Examples

Hints

More Two Pointers problems

Problem

Input, output and limits

Examples

Hints

More Two Pointers problems