FJ muốn bán N miếng bánh làm từ sữa các con bò (1<=N<=2000). FJ bán mỗi ngày 1 miếng bánh và muốn nhận được số tiền lớn nhất từ việc bán những cái bánh đó trong 1 khoảng thời gian có hạn. Mỗi miếng bánh có giá trị cao nhờ nhiều nguyên nhân:

-Các miếng bánh được xếp trong 1 băng dài được đánh số từ 1 đến N. Mỗi ngày, FJ có thể lấy 1 miếng bánh ở đầu này hoặc đầu kia của băng đó.

-Cũng giống như rượu và pho mát, các miếng bánh càng có tuổi thọ cao thì càng có giá trị.

-Giá trị các miếng bánh cũng không cố định. Miếng bánh thứ i có giá trị V(i)(1<=V(i)<=1000).

-Mỗi miếng bánh có giá trị phụ thuộc vào tuổi của nó. Mỗi con bò sẽ nhận được a*V(i) với miếng bánh thứ i có a tuổi.

Cho các giá trị V(i). Tìm giá trị lớn nhất FJ có thể nhận được từ việc bán bánh. Miếng bánh được bán đầu tiên sẽ có tuổi là 1. Các miếng bánh sau đó sẽ nhiều hơn miếng trước 1 tuổi

Input

Dòng thứ nhất: 1 số tự nhiên N duy nhất.

N dòng tiếp theo mỗi dòng ghi giá trị V(i)

Output

1 số duy nhất là giá trị lớn nhất mà FJ thu được từ việc bán bánh

Example

Input:
5

1

3

1

5

2

Output:
43