Background

When you see this time limit, there is no need to panic. This problem does not rely on constant-factor tricks.

Problem Description

You are given a sequence $a_i$ of length $n$ (indices start from $1$). You need to choose a non-empty subsequence $p$ of $\{1,2,3,\cdots,n\}$ with any length. Let the length of $p$ be $l$. Define $a_0=p(0)=a_{n+1}=0,p(l+1)=n+1$. You need to maximize:

$$\sum_{i=0}^{l}(a_{p(i+1)}-a_{p(i)})(p(l-i+1)-p(l-i))$$

Output the maximum value.

If $a$ is a subsequence of $b$, then $a$ can be obtained by deleting zero or more elements from $b$ while keeping the original order. For example, $\{1,4\}$ is a subsequence of $\{1,2,3,4\}$, $\{3,1,5\}$ is a subsequence of $\{3,1,5\}$, and $\{1,2\}$ is not a subsequence of $\{3,2,1\}$.

Input Format

The first line contains a positive integer $n$, representing the length of $a$.

The second line contains $n$ integers, where the $i$-th number is $a_i$.

Output Format

Output one integer, representing the maximum value of $\sum_{i=0}^{l}(a_{p(i+1)}-a_{p(i)})(p(l-i+1)-p(l-i))$.

3
1 5 2

2

5
-2 3 2 5 3

15

Hint

[Sample Explanation]

For the first sample, choosing $\{1\}$ gives the maximum result $(1-0)\times(4-1)+(0-1)\times(1-0)=2$.

For the second sample, choosing $\{1,5\}$ gives the maximum result $(-2-0)\times(6-5)+[3-(-2)]\times(5-1)+(0-3)\times(1-0)=15$.

[Constraints]

For $20\%$ of the testdata, $n\le20$ and $0\le a_i\le10^3$.

For $50\%$ of the testdata, $n\le80$.

For $100\%$ of the testdata, $1\le n\le300$ and $-10^9\le a_i\le10^9$.

Translated by ChatGPT 5