Description

There are $N$ distinct positive integers $x_1, x_2, \dots, x_N$ arranged in a row. At each operation, you may remove a consecutive block of $i$ numbers ($1 \le i \le N$) from either the left end or the right end only. After removing, $N - i$ numbers remain; continue applying the same operation until all numbers are removed.

Each operation has a value. Suppose you remove all numbers from position $i$ to position $k$ (inclusive). The operation value is $|x_i - x_k| \times (k - i + 1)$. If you remove exactly one number, the operation value equals the value of that number.

Find how to operate to obtain the maximum possible total value, and output that maximum total value.

Input Format

• The first line contains a positive integer $N$.
• The second line contains $N$ space-separated distinct positive integers.

Output Format

Output one line containing a single positive integer: the maximum total value.

6
54 29 196 21 133 118

768

Hint

Sample explanation and notes

It is possible to achieve the maximum value in 3 operations. First, remove the first 3 numbers: $54$, $29$, $196$, with operation value 426. Second, among the remaining three numbers $(21, 133, 118)$, remove the last number $118$, with operation value $118$. Third, remove the remaining two numbers $21$ and $133$, with operation value $224$. The total operation value is $426 + 118 + 224 = 768$.

Constraints

$3 \le N \le 100$, $1 \le x_i \le 1000$.

Translated by ChatGPT 5