Tý có một công ty xây dựng đang thiết kế mặt cắt của một khu đô thị gồm \(N\) toà nhà. Mỗi toà nhà có chiều rộng bằng 1 và chiều cao \(h_i\).

Họ muốn tìm hình chữ nhật có diện tích lớn nhất có thể đặt vừa vào bên trong mặt cắt này (hình chữ nhật phải được bao phủ hoàn toàn bởi các toà nhà, không được nhô ra ngoài).

Nói cách khác, tìm \(\max (r - l + 1) \times \min_{l \le k \le r} h_k\) với mọi \(1 \le l \le r \le N\).

Hãy tính diện tích lớn nhất đó.

Định dạng đầu vào

• Dòng đầu chứa số nguyên \(N\) (\(1 \le N \le 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(h_1, h_2, \dots, h_N\) (\(1 \le h_i \le 10^9\)).

Định dạng đầ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:

7
2 1 4 5 1 3 3

Output:

8

Giải thích: Hình chữ nhật lớn nhất có chiều cao 3, chiều rộng 2 (toà nhà 6-7), diện tích \(6\), hoặc chiều cao 4, rộng 2 (toà nhà 3-4), diện tích \(8\).

Ràng buộc

• Subtask 1 (30%): \(N \le 2000\).
• Subtask 2 (30%): \(N \le 10^4\).
• Subtask 3 (40%): \(N \le 10^5\).