Cho \(n\) phần quà \((1 \le n \le 300)\), mỗi phần quà có điểm thưởng không vượt quá \(10^2\).

Nếu bạn chọn phần quà thứ \(i\) bạn sẽ nhận được điểm thưởng \(nums[i - 1] * nums[i] * nums[i + 1]\). Nếu \(i-1 \lt 0\) hoặc \(i+1 \ge n\) (vượt khỏi mảng) thì xem như phần quà đó có giá trị là \(1\).

Hãy tìm cách chọn quà sao cho tổng giá trị điểm thưởng là lớn nhất

Example

Sample input

4
3 1 5 8

Sample output

167

Giải thích

nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []

total = 3x1x5 + 3x5x8 + 1x3x8 + 1x8x1 = 167