Bạn được cho \(n\) chai bowling xếp theo hàng ngang. Bạn là một siêu sao bowling, có thể ném trúng bất cứ chỗ nào. Đặc biệt, các chai bowling có giá trị. Một trong ba trường hợp sau có thể xảy ra ở chai thứ \(i\):

• Ném trúng chai thứ \(i\) và được \(a_i\) điểm
• Ném trúng giữa chai thứ \(i\) và \(i+1\) và được \(a_i \times a_{i+1}\) điểm
• Không ném ở chai thứ \(i\)

Bạn có thể ném vô số lần và không nhất thiết phải làm đổ.

Yêu cầu

Hãy xác định số điểm lớn nhất mà bạn có thể đạt được.

Input

• Dòng đầu tiên chứa một số nguyên dương \(n(1 \le n \le 2 \cdot 10^5)\) là số chai bowling.
• Dòng tiếp theo là \(n\) số nguyên \(a_i(-10^6 \le a_i \le 10^6)\) là giá trị của chai bowling thứ \(i\).

Output

• Một dòng chứa một số nguyên dương là số điểm lớn nhất mà bạn có thể đạt được.

Example

8
-3 1 1 9 9 2 5 5

110