{"raw_statement":[{"iden":"statement","content":"小 C 有一个长度为 $n$ 的数组 $a$。\n\n小 C 定义，$f(i)$ 为 $a_i$ 的前排名，其中 $f(i)$ 等于数组 $a$ 中大于 $a_i$ 的元素个数加 $1$。\n\n小 C 还定义，$g(i)$ 为 $a_i$ 的后排名，其中 $g(i)$ 等于数组 $a$ 中大于等于 $a_i$ 的元素个数。\n\n每次操作，小 C 需要选择一个不大于 $n$ 的正整数 $t$，并将 $a_t$ 的值增加 $1$。\n\n小 C 想知道，对于每一个 $1 \\le i \\le n$，想要使 $f(i) \\le k \\le g(i)$，最少需要进行多少次操作？\n\n可以证明一定存在至少一种操作方案使得 $f(i) \\le k \\le g(i)$。"},{"iden":"input","content":"第一行三个整数 $c,n,k$，其中 $c$ 表示测试点编号。$c=0$ 表示该测试点为样例。\n\n第二行 $n$ 个整数，表示给定的数组 $a$。"},{"iden":"output","content":"共 $n$ 行，每行一个整数，其中第 $i$ 行的整数表示想要使 $f(i) \\le k \\le g(i)$ 所至少需要进行的操作数。"},{"iden":"note","content":"#### 【样例解释 #1】\n\n当 $i=1$ 时，小 C 可以选择 $t=1$ 并进行 $3$ 次操作。此时 $f(i)=2$，$g(i)=4$，满足 $f(i) \\le k \\le g(i)$。可以证明此时小 C 至少需要进行 $3$ 次操作。\n\n当 $i=4$ 时，小 C 可以选择 $t=3$ 进行 $1$ 次操作，再选择 $t=6$ 进行 $1$ 次操作。此时 $f(i)=1$，$g(i)=3$，满足 $f(i) \\le k \\le g(i)$。可以证明此时小 C 至少需要进行 $2$ 次操作。\n\n#### 【样例 #2】\n\n见附加文件中的 `rank/rank2.in` 与 `rank/rank2.ans`。\n\n该样例满足测试点 $7$ 的限制。\n\n#### 【样例 #3】\n\n见附加文件中的 `rank/rank3.in` 与 `rank/rank3.ans`。\n\n该样例满足测试点 $20$ 的限制。\n\n#### 【数据范围】\n\n对于 $100\\%$ 的数据，$1 \\le k \\le n \\le 5 \\times 10^5$，$1 \\le a_i \\le 10^9$。\n\n|测试点编号|$n \\le$|$a_i \\le$|特殊性质|\n|:---:|:---:|:---:|:---:|\n|$1\\sim6$|$2000$|$10^9$|A|\n|$7\\sim10$|$2000$|$10^9$|无|\n|$11\\sim14$|$5\\times10^5$|$10^9$|B|\n|$15\\sim20$|$5\\times10^5$|$10^9$|无|\n\n特殊性质 A：保证对于所有的 $1 \\le i \\lt n$，都有 $a_i \\ge a_{i+1}$。\n\n特殊性质 B：保证 $k=1$。"}],"translated_statement":null,"sample_group":[["0 6 3\n1 1 4 5 1 4","3\n3\n0\n2\n3\n0"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}