Bán bình gốm cổ

Bác Sắn có \(N\) chiếc bình gốm cổ được xếp thẳng hàng trong một chiếc hộp dài mở hai đầu, bình thứ \(i\) có giá trị gốc \(v_i\). Mỗi ngày bác chỉ bán được một bình và chỉ được lấy bình ở đầu trái hoặc đầu phải của hàng bình còn lại.

Bình càng để lâu càng quý: nếu bình có giá trị gốc \(v\) được bán vào ngày thứ \(a\) (ngày đầu tiên là \(a = 1\)) thì bác thu được \(v \cdot a\) đồng.

Hãy tìm cách bán hết \(N\) bình để tổng số tiền thu được là lớn nhất, và in ra số tiền đó.

Input

• Dòng đầu chứa số nguyên \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(v_1, v_2, \dots, v_N\) theo thứ tự xếp trong hộp.

Output

In ra một số nguyên là tổng tiền lớn nhất có thể thu được.

Constraints

• \(1 \le N \le 2000\)
• \(1 \le v_i \le 1000\)

Sample Input

6
2 7 3 1 9 4

Sample Output

103

Explanation

Cách bán tối ưu: lấy bình ở đầu trái bốn lần, rồi lấy hai bình ở đầu phải. Thứ tự bán là \(2, 7, 3, 1, 4, 9\) vào các ngày \(1, \dots, 6\): \(2\cdot1 + 7\cdot2 + 3\cdot3 + 1\cdot4 + 4\cdot5 + 9\cdot6 = 103\).