Cho ~n~ số nguyên dương ~a_i, i = 1 \dots n~, bạn phải đặt giữa ~n~ số nguyên dương 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 \times 1 + 5 \times 3~ ~4 \times 7 \times 1 + 5 + 3~

Chú ý: Không được thay đổi thứ tự xuất hiện của ~a_i, i = 1 \dots n~ trong biểu thức thu được.

Yêu cầu: Tìm giá trị lớn nhất của biểu thức thu được sau khi đặt các phép toán.

Input

• Dòng 1 chứa số nguyên dương ~n~ (~4 \le n \le 1.000~)
• ~n~ dòng tiếp theo, dòng thứ ~i + 1~ chứa số nguyên dương ~a_i~ (~1 \le a_i \le 10.000, i = 1 \dots n~)

Output

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

Sample Input 1

5
4
7
1
5
3

Sample Output 1

44