Collecting Energy

Interview

Time limit1sMemory limit512 MB

Summary

Given a row of N weighted beads (N up to 10), remove interior beads one at a time, scoring the product of the neighbors left and right, and maximize the total score.

Level: Medium4 of 10
Topics: Dynamic programming, Recursion, Brute force
Solved: No attempts yet

Problem

N energy beads are placed in a row, and you want to collect energy using these beads.

The weight of the i-th energy bead is Wi, and the method for collecting energy is as follows. It can be used repeatedly.

Choose one energy bead. Let x be the index of the chosen energy bead. The first and last energy beads cannot be chosen.
Remove the x-th energy bead.
You can collect Wx-1 × Wx+1 energy.
Decrease N by 1, and renumber the energy beads from 1 to N. The numbering must be assigned so that the first bead is 1, the next bead is 2, and so on.

Given N and the weights of the energy beads, write a program to find the maximum amount of energy that can be collected.

Input

The first line gives the number of energy beads N (3 ≤ N ≤ 10).

The second line gives the weights of the energy beads W1, W2, ..., WN separated by spaces. (1 ≤ Wi ≤ 1,000)

Output

Print the maximum amount of energy that can be collected on the first line.

Examples4

Example 1
Input
```
4
1 2 3 4
```
Expected output
```
12
```
Example 2
Input
```
5
100 2 1 3 100
```
Expected output
```
10400
```
Example 3
Input
```
7
2 2 7 6 90 5 9
```
Expected output
```
1818
```
Example 4
Input
```
10
1 1 1 1 1 1 1 1 1 1
```
Expected output
```
8
```