Background

Informational problems make us better.

Problem Description

Define the joint value of two sequences $\{a_n\}$ and $\{b_n\}$ as

$$\operatorname{unval}(a,b)=\sum_{i=1}^nb_i(b_i-a_i)$$

Now you are given a sequence $\{a_n\}$. Find a non-decreasing sequence $\{b\}$ that minimizes $\operatorname{unval}(a,b)$. You only need to output the value of $\operatorname{unval}(a,b)$.

Note that the elements in $\{b\}$ do not have to be integers.

Input Format

The first line contains a positive integer $n$.

The second line contains $n$ integers $a_i$.

Output Format

Output one line with the answer.

5
1 2 3 4 5

-13.7500000

10
1000 1 2 8 9 5 4 1000 -40 1000

-403015.7500000

Hint

Hint: If you do not know how to solve this problem, you can ask APJifengc.

---

Explanation for Sample 1: the $\{b\}$ that makes the joint value minimal is 0.5 1 1.5 2 2.5.

---

Constraints and notes:

$$\newcommand{\arraystretch}{1.5} \begin{array}{c|c|c|c}\hline\hline \textbf{Subtask} & \bm{n}\le & \textbf{Score} & \textbf{Special property}\\\hline \textsf{1} & 100 & 10 & \textbf{None} \\\hline \textsf{2} & 10^6 & 5 & \{a\}\textbf{ All equal} \\\hline \textsf{3} & 10^6 & 5 & \{a\}\textbf{ Non-decreasing} \\\hline \textsf{4} & 10^4 & 30 & \textbf{None} \\\hline \textsf{5} & 10^6 & 50 & \textbf{None} \\\hline\hline \end{array}$$

For all testdata, $1\le n\le 10^6$ and $|a_i|\le 10^3$.

---

Scoring rules:

This problem uses Special Judge. If your answer is $pans$ and the standard answer is $cans$, then you will get

$$\min\Bigg\{100,\Bigg\lfloor\dfrac{0.1}{\min\Big\{|pans-cans|,\Big|\dfrac{|pans-cans|}{cans}\Big|\Big\}}\Bigg\rfloor\Bigg\}$$

points.

Tests are bundled within each Subtask. That is, the minimum score among the tests in the Subtask is taken as the Subtask score.

Translated by ChatGPT 5