Có n ngôi nhà xây dựng cạnh nhau trên một đường dài, mỗi ngôi nhà có chiều rộng bằng 1, chiều cao bằng hᵢ (1 ≤ i ≤ n).

Nếu ghép k ngôi nhà cạnh nhau thành một khối thì ta được một khối nhà hình chữ nhật có diện tích:

k × min(hᵢ, hᵢ₊₁, …, hᵢ₊ₖ₋₁)

Yêu cầu: Hãy tìm diện tích lớn nhất có thể.

INPUT

• Dòng đầu tiên chứa số nguyên dương n (2 ≤ n ≤ 10⁵);
• Dòng thứ hai chứa n số nguyên dương h₁, h₂, …, hₙ (1 ≤ hᵢ ≤ 10⁶).

OUTPUT

Ghi ra một số nguyên duy nhất là diện tích lớn nhất tìm được.

Ví dụ

Sample Input

6
2 1 5 6 2 3

Sample Output

10

Giải thích