『STA - R1』Crossnews
题目背景
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$。
输出格式
一行一个答案。
输入输出样例
输入样例 #1
5
1 2 3 4 5输出样例 #1
-13.7500000输入样例 #2
10
1000 1 2 8 9 5 4 1000 -40 1000输出样例 #2
-403015.7500000说明
提示：如果你不会做这道题，可以问问 [APJifengc](/user/279652)。
***
样例 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 得分。