Team Building

Interview

Time limit1sMemory limit1024 MB

Summary

Given N developers in a line with powers, pick two so that the gap between them times the smaller power is maximized.

Level: Medium6 of 10
Topics: Array, Two pointers, Greedy, Sorting
Solved: No attempts yet

Problem

$N$ developers stand in a line to build teams.

A team is formed by exactly two developers.

When developer A and developer B form a team, the team's power is computed as follows.

(the number of other developers between developer A and developer B) × min(the power of developer A, the power of developer B)

For example, suppose there are 4 developers with powers 1 4 2 5. If the developer with power 1 and the developer with power 5 form a team, the team's power is $2×min(1, 5) = 2$ .

Find the maximum power among all teams that can be formed in team building.

Input

The first line gives the number of developers $N$ .

The second line gives the powers $x_{i}$ of the $N$ developers, separated by spaces.

Output

Print the maximum team power.

Constraints

$2 ≤ N ≤ 100,000$
$1 ≤ x_i ≤ 10,000$ , $x_i$ is an integer

Examples1

Example 1
Input
```
4
1 4 2 5
```
Expected output
```
4
```