Adjacent Product Game

Time limit1sMemory limit64 MB

Summary

Choose a subsequence of the given numbers to maximize the sum of products of adjacent chosen pairs.

Level: Medium7 of 10
Topics: Dynamic programming, Greedy
Solved: No attempts yet

Problem

Mirko writes $N$ numbers on a very long sheet of paper. Slavko then takes a pencil and crosses out some of them. Every number that is not crossed out is copied to a new sheet in the original order, and Slavko's score is the sum of the products of each pair of neighboring numbers on the new sheet.

For example, if the copied sequence is $3, 6, -1, 2$ , then the score is $3 \times 6 + 6 \times (-1) + (-1) \times 2 = 10$ . If fewer than two numbers are copied, the score is $0$ .

Slavko does not know which numbers to cross out to reach the highest score. Write a program that finds the largest score Slavko can reach. There is no limit on how many numbers he crosses out.

Input

The first line contains $N$ , the count of numbers Mirko wrote. ( $3 \le N \le 30000$ )

Each of the next $N$ lines contains one number $X_i$ from Mirko's paper, written with exactly two decimal digits and padded with a trailing zero when needed. ( $-10.00 \le X_i \le 10.00$ )

Output

Print the largest score Slavko can reach on the first and only line. Print it with exactly four decimal digits.

Every $X_i$ has two decimal digits, so the score is always a multiple of $0.0001$ .

Examples3

Example 1
Input
```
3
8.52
1.00
9.61
```
Expected output
```
81.8772
```
Example 2
Input
```
5
1.00
2.00
3.00
4.00
5.00
```
Expected output
```
40.0000
```
Example 3
Input
```
3
-1.25
10.00
-1.00
```
Expected output
```
1.2500
```