Biểu thức

Cho \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\).
Bạn phải đặt giữa các số này đúng hai phép nhân và \(n-3\) phép cộng để giá trị biểu thức thu được là lớn nhất.
(Không được thay đổi thứ tự các số.)

Ví dụ, với \(n = 5\) và dãy số \(4, 7, 1, 5, 3\), ta có thể đặt:
\(4 \times 7 + 1 + 5 \times 3\) hoặc \(4 \times 7 \times 1 + 5 + 3\).

Input

Dòng đầu chứa số nguyên \(n\) (\(4 \le n \le 500\)).

\(n\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(a_i\) (\(1 \le a_i \le 10^4\)).

Output

Ghi ra một số nguyên dương --- giá trị lớn nhất của biểu thức thu được.

Example

Input:

5
4
7
1
5
3

Output:

44