Practice Sequences with the exercise "The Beautiful sequence"

Learning Opportunities

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

Sequences

Statement

Goal

We define the beautiful value of an integer sequence as the product of the value of its smallest element and its length. You are given an integer sequence containing N elements, and you should find out one of its continuous subsequences, such that it has the largest beautiful value among all the continuous subsequences.

You may solve this problem with an O(N) algorithm.

Input

Line 1: A single integer N, indicating the length of the sequence.
Line 2: N integers indicating the sequence.

Output

Line 1: The largest beautiful value you can find. (Note you don't need to output the subsequence itself.)

Constraints

1 <= N <= 500
The value of the elements is between 0 and 10000, inclusive.

Example

Input

3
1 2 3

Output

Solve it

A higher resolution is required to access the IDE