Hình chữ nhật lớn nhất trong biểu đồ

Buổi 03 — Mảng 1 Chiều
Points
28
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
array1d
Submissions
Đề bài

Cho biểu đồ cột gồm $n$ cột liền kề nhau có chiều rộng bằng $1$ và chiều cao lần lượt là $H_1, H_2, \dots, H_n$. Hãy tìm diện tích lớn nhất của một hình chữ nhật nằm hoàn toàn bên trong biểu đồ cột.

Dữ liệu vào

Dòng đầu chứa số nguyên $n$. Dòng thứ hai chứa $n$ số nguyên không âm $H_1, H_2, \dots, H_n$.

Dữ liệu ra

Một số nguyên duy nhất là diện tích hình chữ nhật lớn nhất.

Ví dụ

Input

6
2 1 5 6 2 3

Output

10
Giới hạn

$1 \le n \le 2 \cdot 10^5$, $0 \le H_i \le 10^9$.

Draft saved