- 25

## 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.

Please 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<=

The value of the elements is between 0 and 10000, inclusive.

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

Example

Input

3 1 2 3

Output

4

A higher resolution is required to access the IDE

Online Participants

### Channels

### Direct Messages

No private conversations