Most water between two walls

Problem

A hostel courtyard has n concrete walls in a row, one metre apart. Wall i has height h[i] metres. During the monsoon, the students want to block water between two walls to make a small pool. The water level cannot go above the shorter of the two walls. The amount of water is the distance between the two walls times that level. Print the largest amount of water any two walls can hold.

Input, output and limits

Input: The first line has one integer n. The second line has n integers: the heights h[1] to h[n].
Output: One integer: the largest value of (j − i) × min(h[i], h[j]) over all pairs of walls i < j.
Constraints: 2 ≤ n ≤ 10^5
0 ≤ h[i] ≤ 10^9

Examples

Example

Input

9
1 8 6 2 5 4 8 3 7

Output

Walls 2 and 9 have heights 8 and 7. They are 7 apart, so they hold 7 × 7 = 49.

Hints

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

Hint 1

Start with the widest pair: the first wall and the last wall.

Hint 2

The water level is set by the shorter wall. Moving the taller wall inward can only make the width smaller without raising the level.

Hint 3

So move the shorter wall inward, compute the new amount, and keep the best one seen.

Hint 4

Stop when the two indexes meet. Use long for the amount.

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

Solve in the editor

All Java problems

Problem

Input, output and limits

Examples

Hints

More Two Pointer problems

Problem

Input, output and limits

Examples

Hints

More Two Pointer problems