「MXOI Round 2」排名

小 C 有一个长度为 $n$ 的数组 $a$。 小 C 定义，$f(i)$ 为 $a_i$ 的前排名，其中 $f(i)$ 等于数组 $a$ 中大于 $a_i$ 的元素个数加 $1$。 小 C 还定义，$g(i)$ 为 $a_i$ 的后排名，其中 $g(i)$ 等于数组 $a$ 中大于等于 $a_i$ 的元素个数。 每次操作，小 C 需要选择一个不大于 $n$ 的正整数 $t$，并将 $a_t$ 的值增加 $1$。 小 C 想知道，对于每一个 $1 \le i \le n$，想要使 $f(i) \le k \le g(i)$，最少需要进行多少次操作？ 可以证明一定存在一种操作方案使得 $f(i) \le k \le g(i)$。

第一行三个整数 $c,n,k$，其中 $c$ 表示测试点编号。$c=0$ 表示该测试点为样例。 第二行 $n$ 个整数，表示给定的数组 $a$。

共 $n$ 行，每行一个整数，其中第 $i$ 行的整数表示想要使 $f(i) \le k \le g(i)$ 所至少需要进行的操作数。

0 6 3
1 1 4 5 1 4

3
3
0
2
3
0

#### 【样例解释 #1】 当 $i=1$ 时，小 C 可以选择 $t=1$ 并进行 $3$ 次操作。此时 $f(i)=2$，$g(i)=4$，满足 $f(i) \le k \le g(i)$。可以证明此时小 C 至少需要进行 $3$ 次操作。 当 $i=4$ 时，小 C 可以选择 $t=3$ 进行 $1$ 次操作，再选择 $t=6$ 进行 $1$ 次操作。此时 $f(i)=1$，$g(i)=3$，满足 $f(i) \le k \le g(i)$。可以证明此时小 C 至少需要进行 $2$ 次操作。 #### 【样例 #2】 见附加文件中的 `rank/rank2.in` 与 `rank/rank2.ans`。 该样例满足测试点 $7$ 的限制。 #### 【样例 #3】 见附加文件中的 `rank/rank3.in` 与 `rank/rank3.ans`。 该样例满足测试点 $20$ 的限制。 #### 【数据范围】 对于 $100\%$ 的数据，$1 \le k \le n \le 5 \times 10^5$，$1 \le a_i \le 10^9$。 |测试点编号|$n \le$|$a_i \le$|特殊性质| |:---:|:---:|:---:|:---:| |$1\sim6$|$2000$|$10^9$|A| |$7\sim10$|$2000$|$10^9$|无| |$11\sim14$|$5\times10^5$|$10^9$|B| |$15\sim20$|$5\times10^5$|$10^9$|无| 特殊性质 A：保证对于所有的 $1 \le i \lt n$，都有 $a_i \ge a_{i+1}$。 特殊性质 B：保证 $k=1$。