Cho một biểu đồ (histogram) gồm ~N~ cột liền kề nhau, cột thứ ~i~ có chiều rộng bằng ~1~ và chiều cao tương ứng là ~H[i]~.

Hãy tìm diện tích của hình chữ nhật lớn nhất có thể nằm trọn trong biểu đồ này. Các cạnh của hình chữ nhật phải song song với các trục tọa độ.

Dữ liệu

• Dòng đầu tiên chứa số nguyên dương ~N~ (~1 \le N \le 10^5~).
• Dòng thứ hai chứa ~N~ số nguyên không âm ~H[1], H[2], ..., H[N]~ (~0 \le H[i] \le 10^9~). Các số được phân cách nhau bởi khoảng trắng.

Kết quả

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

(Lưu ý: Kết quả có thể vượt quá giới hạn của số nguyên 32-bit, hãy sử dụng kiểu dữ liệu số nguyên 64-bit như long long trong C++).

Ví dụ

Input

6
2 1 5 6 2 3

Output

10

Giải thích

Hình chữ nhật lớn nhất được tạo bởi 2 cột có chiều cao 5 và 6. Chiều cao của hình chữ nhật bị giới hạn bởi cột thấp hơn là 5. Chiều rộng của hình chữ nhật là 2. Diện tích lớn nhất = ~5 \times 2 = 10~.