Bé Bin có một bộ sưu tập đá huyền bí. Mỗi cục đá có một đặc trưng năng lượng riêng. Một ngày đẹp trời, bé Bin quyết định lấy bộ sưu tập đá của mình ra, sắp xếp chúng thành một hàng gồm N cục đá. Và bé Bin quyết định chơi trò chơi như sau:

Cứ mỗi đợt lượt chơi, bé Bin sẽ chọn một cục đá ở vị trí thứ \(x\) bất kì \((1 < x < N)\), sau đó bé Bin sẽ vứt cục đá \(x\) đó ra khỏi hàng, đồng thời bé Bi sẽ nhận được một lượng năng lượng tương đương là \(c[x−1]*c[x+1]\) với \(c[x]\) là năng lượng của viên đá thứ \(x\). Sau khi cục đá thứ \(x\) bị vứt đi, bé Bin sẽ đánh số các cục đá lại từ đầu theo thứ tự bắt đầu từ 1 từ trái sang phải. Khi trên mặt đất chỉ còn hai cục đá thì bé Bi sẽ kết thúc trò chơi.

Yêu cầu: Cho biết số lượng viên đá trên mặt đất và mức năng lượng của chúng. Hãy giúp bé Bin tìm được tổng năng lượng lớn nhất sau khi chơi trò chơi này nhé !

Dữ liệu

• Dòng đầu tiên gồm một số nguyên N là số lượng viên đá \((3 ≤ N ≤ 100)\).

• Dòng tiếp theo gồm \(N\) số nguyên dương, số nguyên dương thứ \(i\) là giá trị \(c[i] (1 ≤ c[i] ≤ 1000)\).

Kết quả:

Gồm một dòng duy nhất là tổng năng lượng lớn nhất mà bé Bin có thể nhận được.

Sample Input

4 
1 2 3 4

Sample Output

12

Giải thích

Bé Bin sẽ vứt viên đá thứ 3 đi, nhận được 2 × 4 = 8 đơn vị năng lượng ⇒ dãy đá còn lại là 1 2 4 
Bé Bin vứt viên đá thứ 2 đi, nhận được 1 × 4 = 4 đơn vị năng lượng ⇒ dãy đá còn lại là 1 4, trò chơi kết thúc. Kết quả : 8 + 4 = 12 đơn vị năng lượng.