Cho dãy \(a\) gồm \(n\) số nguyên, bạn phải đặt giữa \(n\) số nguyên này \(2\) phép nhân và \(n-3\) phép cộng sao cho kết quả biểu thức là lớn nhất.

Ví dụ: với \(n=5\) và dãy \(a_i\) là \(4, 7, 1, 5, 3\) thì bạn có thể có các biểu thức:

• \(4 + 7 \cdot 1 + 5 \cdot 3\)
• \(4 \cdot 7 + 1 + 5 \cdot 3\)

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(4 \leq n \leq 10^3\)).
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa số nguyên \(a_i\) (\(1 \leq a_i \leq 10^4\)).

Output

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

Example

5
4
7
1
5
3

44