Một biểu đồ Histogram gồm N cột đứng liên tiếp. Mỗi cột có chiều rộng bằng 1, cột thứ i có chiều cao ~H_i~.

Một hình chữ nhật được gọi là hợp lệ nếu:

• Hai cạnh của hình chữ nhật song song với các trục của biểu đồ.
• Hình chữ nhật nằm hoàn toàn bên trong các cột của Histogram.
• Hình chữ nhật có thể trải trên một hoặc nhiều cột liên tiếp.

Hãy tìm diện tích lớn nhất của một hình chữ nhật hợp lệ có thể tạo được trong Histogram.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên N — số cột của Histogram.
• Dòng thứ hai chứa N số nguyên ~H_1,H_2,\ldots,H_N~, trong đó ~H_i~ là chiều cao của cột thứ i.

Kết quả ra

In ra một số nguyên duy nhất là diện tích lớn nhất của hình chữ nhật có thể tạo được.

Giới hạn

• 1 ≤ N ≤ ~2⋅10^5~

• 1 ≤ ~H_i~ ≤ ~10^9~

Lưu ý: Kết quả có thể vượt quá phạm vi của kiểu số nguyên 32 bit.

Ví dụ

Input

6
2 1 5 6 2 3

Output

10

Giải thích

Chọn hai cột liên tiếp có chiều cao 5 và 6.

Chiều cao lớn nhất của hình chữ nhật nằm hoàn toàn trong hai cột này là:

min(5,6)=5.

Chiều rộng của hình chữ nhật là 2, nên diện tích bằng:

5×2=10.

Không tồn tại hình chữ nhật nào có diện tích lớn hơn, vì vậy đáp án là 10.