Maximizing Weighted Difference Sum in a Subsequence

You are given a sequence \(a_1,a_2,\dots,a_n\) of length \(n\) with indices starting from \(1\). You need to choose an arbitrary non‐empty subsequence of indices from \(\{1,2,3,\dots,n\}\). Suppose the chosen subsequence is \(p\) with length \(l\). Define

[ \begin{aligned} &p(0)=0,\quad p(l+1)=n+1,\ &a_0=a_{n+1}=0. \end{aligned} ]

Then, the score is defined as

[ S=\sum_{i=0}^{l} (a_{p(i+1)}-a_{p(i)})\Bigl(p(l-i+1)-p(l-i)\Bigr). ]

Your task is to choose a subsequence \(p\) (note that a subsequence is obtained by deleting zero or more elements from \(\{1,2,\dots,n\}\) without changing the order) so that the value of \(S\) is maximized. Output the maximum possible value.

Note: A sequence \(a\) is a subsequence of \(b\) if it can be obtained by deleting zero or more elements from \(b\) without changing the order. For example, \(\{1,4\}\) is a subsequence of \(\{1,2,3,4\}\), but \(\{1,2\}\) is not a subsequence of \(\{3,2,1\}\).

inputFormat

The first line contains an integer \(n\) (the length of the sequence). The next line contains \(n\) space-separated integers \(a_1,a_2,\dots,a_n\).

outputFormat

Output a single integer: the maximum possible value of the expression \(S\).

sample

1
5

0