P8879 "STA - R1" Crossnews

Informational problems make us better.

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.

The first line contains a positive integer $n$. The second line contains $n$ integers $a_i$.

Output one line with the answer.

Hint: If you do not know how to solve this problem, you can ask [APJifengc](/user/279652). *** 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