P9587 "MXOI Round 2" Ranking

Xiao C has an array $a$ of length $n$. Xiao C defines $f(i)$ as the front rank of $a_i$, where $f(i)$ equals the number of elements in array $a$ that are greater than $a_i$, plus $1$. Xiao C also defines $g(i)$ as the back rank of $a_i$, where $g(i)$ equals the number of elements in array $a$ that are greater than or equal to $a_i$. In each operation, Xiao C needs to choose a positive integer $t$ not greater than $n$, and increase the value of $a_t$ by $1$. Xiao C wants to know, for each $1 \le i \le n$, in order to make $f(i) \le k \le g(i)$ hold, what is the minimum number of operations needed? It can be proven that there is always at least one sequence of operations that makes $f(i) \le k \le g(i)$.

The first line contains three integers $c,n,k$, where $c$ indicates the test point ID. $c=0$ means this test point is the sample. The second line contains $n$ integers, representing the given array $a$.

Output $n$ lines in total, each containing one integer. The integer on line $i$ indicates the minimum number of operations needed to make $f(i) \le k \le g(i)$ hold.

#### Sample Explanation #1 When $i=1$, Xiao C can choose $t=1$ and perform $3$ operations. Then $f(i)=2$ and $g(i)=4$, satisfying $f(i) \le k \le g(i)$. It can be proven that Xiao C needs at least $3$ operations in this case. When $i=4$, Xiao C can first choose $t=3$ and perform $1$ operation, then choose $t=6$ and perform $1$ operation. Then $f(i)=1$ and $g(i)=3$, satisfying $f(i) \le k \le g(i)$. It can be proven that Xiao C needs at least $2$ operations in this case. #### Sample #2 See `rank/rank2.in` and `rank/rank2.ans` in the attachment. This sample satisfies the constraints of test point $7$. #### Sample #3 See `rank/rank3.in` and `rank/rank3.ans` in the attachment. This sample satisfies the constraints of test point $20$. #### Constraints For $100\%$ of the data, $1 \le k \le n \le 5 \times 10^5$, and $1 \le a_i \le 10^9$. |Test Point ID|$n \le$|$a_i \le$|Special Property| |:---:|:---:|:---:|:---:| |$1\sim6$|$2000$|$10^9$|A| |$7\sim10$|$2000$|$10^9$|None| |$11\sim14$|$5\times10^5$|$10^9$|B| |$15\sim20$|$5\times10^5$|$10^9$|None| Special Property A: It is guaranteed that for all $1 \le i \lt n$, $a_i \ge a_{i+1}$ holds. Special Property B: It is guaranteed that $k=1$. Translated by ChatGPT 5