Optimal End Removal Value

Given a sequence of N distinct positive integers \(x_1, x_2, \dots, x_N\) arranged in a row, you are allowed to remove a contiguous block of numbers from either the left end or the right end of the current sequence. Formally, in each operation, you may remove a block of length \(i\ (1 \le i \le L)\) from either end (where \(L\) is the current length of the sequence). Let the block removed be \(x_i, x_{i+1}, \dots, x_k\) (with \(k-i+1=i\)).

The operation value is defined as follows:

• If the block contains only one number (i.e. \(i=k\)), then the operation value is \(x_i\).
• If the block contains more than one number, then the operation value is \[ |x_i - x_k| \times (k-i+1) \] in \(\LaTeX\) format.

After each removal, the remaining numbers retain their order. This process is repeated until all numbers have been removed. Your task is to determine the maximum total value achievable by performing these operations in an optimal order.

inputFormat

The first line contains an integer \(N\) (the number of integers).
The second line contains \(N\) space-separated positive integers \(x_1, x_2, \dots, x_N\).

outputFormat

Output a single integer, the maximum total operation value.

sample

1
10

10