Minimizing the Joint Weight of Two Sequences

Given a sequence \(\{a_n\}\), we want to construct a non-decreasing sequence \(\{b_n\}\) (i.e. \(b_1 \le b_2 \le \cdots \le b_n\)) that minimizes the joint weight defined by

\[ \operatorname{unval}(a,b)=\sum_{i=1}^n b_i(b_i-a_i). \]

Note: The elements of \(\{b_n\}\) do not have to be integers. Output only the minimum value of \(\operatorname{unval}(a,b)\).

Hint: By completing the square, we note that \[ b_i^2 - a_i b_i = \Bigl(b_i-\frac{a_i}{2}\Bigr)^2 -\frac{a_i^2}{4}. \] Thus, minimizing \(\operatorname{unval}(a,b)\) is equivalent to minimizing the expression \[ \sum_{i=1}^n \Bigl(b_i-\frac{a_i}{2}\Bigr)^2 \] subject to \(b_1\le b_2\le \cdots \le b_n\). This is a classical isotonic regression problem that can be solved by the Pool Adjacent Violators Algorithm (PAVA).

inputFormat

The input consists of two lines:

• The first line contains an integer \(n\) (the length of the sequence).
• The second line contains \(n\) space-separated numbers representing the sequence \(a_1, a_2, \ldots, a_n\).

outputFormat

Output a single number which is the minimum value of \(\operatorname{unval}(a,b)=\sum_{i=1}^n b_i(b_i-a_i)\) for an optimal non-decreasing sequence \(\{b_n\}\). The answer may be a real number.

sample

3
1 2 3

-3.5