Giả sử bạn là một kiến trúc sư đang thiết kế địa hình biểu diễn bằng biểu đồ cột cho một dự án xây dựng mới. Biểu đồ cột gồm các cột có chiều cao khác nhau, mỗi cột có chiều rộng là $1$ . Bạn được yêu cầu tìm vùng có thể xây dựng công trình với diện tích lớn nhất trên địa hình.

Trong biểu đồ cột biểu diễn địa hình này, bạn cần tìm vùng hình chữ nhật có diện tích lớn nhất. Cụ thể, bạn cần tìm một nhóm các cột liên tiếp sao cho vùng hình chữ nhật tạo bởi các cột này có diện tích lớn nhất. Hãy tính và in ra diện tích lớn nhất đó.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $n$ ( $1 \le n \le 10^5$ ), biểu thị số cột trong biểu đồ cột.

Dòng thứ hai chứa $n$ số nguyên không âm $h_1, h_2, \dots, h_n$ ( $0 \le h_i \le 10^9$ ), lần lượt biểu thị chiều cao của từng cột.

Dữ liệu ra

In ra một số nguyên, biểu thị diện tích của vùng có thể xây công trình với diện tích lớn nhất trên địa hình này.

Ví dụ

Input

6
2 1 5 6 2 3

Output

10

Ghi chú

Giới hạn dữ liệu

• $2 \le n \le 10^5$

• $2 \le h_i \le 10^5$