题目背景

Informational problems make us better.

题目描述

定义两个序列 $\{a_n\}$，$\{b_n\}$ 的联合权值为

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

现给定一个序列 $\{a_n\}$，求满足 $\operatorname{unval}(a,b)$ 最小的单调不减序列 $\{b\}$，只需输出 $\operatorname{unval}(a,b)$ 的值即可。

注意，$\{b\}$ 中的元素不一定要为整数。

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个整数表示 $a_i$。

输出格式

一行一个答案。

5
1 2 3 4 5

-13.7500000

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

-403015.7500000

提示

提示：如果你不会做这道题，可以问问 APJifengc。

---

样例 1 解释：使得联合权值取到最小值的 $\{b\}$ 为 0.5 1 1.5 2 2.5。

---

数据范围和约定：

$$\newcommand{\arraystretch}{1.5} \begin{array}{c|c|c|c}\hline\hline \textbf{Subtask} & \bm{n}\le & \textbf{分值} & \textbf{特殊性质}\\\hline \textsf{1} & 100 & 10 & \textbf{无} \\\hline \textsf{2} & 10^6 & 5 & \{a\}\textbf{ 全部相等} \\\hline \textsf{3} & 10^6 & 5 & \{a\}\textbf{ 单调不减} \\\hline \textsf{4} & 10^4 & 30 & \textbf{无} \\\hline \textsf{5} & 10^6 & 50 & \textbf{无} \\\hline\hline \end{array} $$

对于全部数据，有 $1\le n\le 10^6$，$|a_i|\le 10^3$。

---

评分规则：

本题使用 Special Judge，如果你的答案是 $pans$，标准答案是 $cans$，则你将获得

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

分。

每个 Subtask 内捆绑测试。即取 Subtask 内得分最小的作为 Subtask 得分。