P2659 Beautiful Sequence

GD is someone who loves seeking beautiful things. One day he obtained a beautiful sequence.

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.

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 a single integer, the "beauty coefficient" of the sequence.

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