Beauty Factor of a Sequence

Given a sequence of positive integers, we define the beauty of any subarray (interval) \([l, r]\) as the product of the length of the subarray and the minimum value within that subarray. In other words, the beauty of the interval \([l, r]\) is:

$$\text{Beauty} = (r - l + 1) \times \min(a_l, a_{l+1}, \dots, a_r) $$

The beauty factor of the whole sequence is the maximum beauty among all possible intervals. Your task is to compute the beauty factor of a given sequence.

inputFormat

The first line of input contains a single integer n denoting the number of elements in the sequence. The second line contains n space-separated positive integers representing the sequence.

outputFormat

Output a single integer, the beauty factor of the sequence.

sample

5
3 1 6 4 5

12

</p>