Cho mảng \(A\) gồm \(n\) số nguyên. Định nghĩa:

\(f(l, r) = (r - l + 1) × min(A_l, A_{l+1}, ..., A_r)\)

Hãy tìm giá trị \(f(l, r)\) lớn nhất với \(1 \le l \le r \le n\).

Dữ liệu vào

• Dòng đầu tiên gồm số nguyên \(n\).
• Dòng thứ hai gồm n số nguyên \(A_i\).

Dữ liệu ra

• In ra một số nguyên là giá trị \(f(l, r)\) lớn nhất.

Điều kiện:

• \(1 \le n \le 10^5\).
• \(1 \le A_i \le 10^9\).

Input 1

3
1 2 3

Output

4