Description

To study how beautiful this sequence is, GD defines the "beauty" and the "beauty coefficient" of a sequence.

• For any subarray $[l, r]$ of this sequence, the "beauty" of this subarray is the product of its length and the minimum value within it.
• The "beauty coefficient" of the whole sequence is the maximum "beauty" among all its subarrays.

Now GD wants you to compute the "beauty coefficient" of this sequence.

Input Format

The first line contains an integer $n$, the number of elements in the sequence. The second line contains $n$ integers $a_1, a_2, \dots, a_n$, describing the sequence.

Output Format

Output a single integer, the "beauty coefficient" of the sequence.

3 
1 2 3

4

Hint

Sample Explanation: Choose the subarray $[2, 3]$ to obtain the maximum "beauty coefficient", which is $2 \times 2 = 4$.

Constraints:

• For $20\%$ of the testdata, $n \le 2 \times 10^3$.
• For $60\%$ of the testdata, $n \le 2 \times 10^5$.
• For $100\%$ of the testdata, $1 \le n \le 2 \times 10^6$, $0 \le a_i \le 2 \times 10^6$.

Hint: You may need fast I/O.

Translated by ChatGPT 5