Vertical lines stand at positions 0, 1, ..., n − 1 with the given heights. Two lines and the ground form a container holding min(h[l], h[r]) × (r − l) units of water. Find the most water any container can hold.
Input
The first line has n (2 ≤ n ≤ 10⁵). The second line has the n heights (0 to 10⁴).
Output
The largest amount of water.
Examples
Example 1 · Input
9 1 8 6 2 5 4 8 3 7
Expected output
49
Example 2 · Input
2 1 1
Expected output
1
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
The area of lines l and r is min(h[l], h[r]) × (r − l).
Hint 2
Start with l at the left end and r at the right end.
Hint 3
Always move the shorter line inward: moving the taller one cannot help.
Solution
Show one correct solution (try it yourself first)
n = int(input())
h = list(map(int, input().split()))
l, r, best = 0, n - 1, 0
while l < r:
best = max(best, min(h[l], h[r]) * (r - l))
if h[l] < h[r]:
l += 1
else:
r -= 1
print(best)