Practice Arrays and Mathematics with the exercise "Max Area"

Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

Statement

Goal

Given n non-negative integers a_1, a_2, ..., a_n, n vertical segments parallel with the y-axis, each vertical lines separated by a distance of 1. Find 2 vertical lines which, with the x-axis, form a rectangular bucket, so that the container holds the most water. Water will spill over the shorter of the two sides.

Example:

With arr = [1, 8, 6, 2, 5, 4, 8, 3, 7]

The bucket with the largest area is created by arr_2 = 8, arr_9 = 7 and x-axis with a max height that can hold water of 7 and the distance between them is 7. So output is 7 * 7 = 49

  |         |
  |~ ~ ~ ~ ~|~ ~|
  |~|~ ~ ~ ~|~ ~|
  |~|~ ~|~ ~|~ ~|
  |~|~ ~|~|~|~ ~|
  |~|~ ~|~|~|~|~|
  |~|~|~|~|~|~|~|
|_|_|_|_|_|_|_|_|

You can create a taller bucket from arr_2 and arr_7, area is 8 * 5 = 40. But it doesn't hold the most area.

Input

Line 1: Integers n
Line 2: n non-negative integers a_1, a_2, ..., a_n separated by spaces

Output

Line 1: An integer for the maximum amount of water the bucket can hold

Constraints

2 <= n <= 1000
0 <= a_i <= 1000

Example

Input

9
1 8 6 2 5 4 8 3 7

Output

Solve it

A higher resolution is required to access the IDE