最小元素之和

题目描述

给你一个长度为 $N$ 的整数序列 $A = (A_1, \dots, A_N)$,以及整数 $M$ 和 $K$。

对每个 $i = 1, \dots, N - M + 1$,解决下面这个独立的问题。

把 $M$ 个整数 $A_i, A_{i + 1}, \dots, A_{i + M - 1}$ 按升序排序后,求前 $K$ 个值的和。

输入格式

输入按以下格式从标准输入给出。

$N$ $M$ $K$
$A_1$ $A_2$ $\ldots$ $A_N$

输出格式

设 $\mathrm{answer}_k$ 为 $i = k$ 时上述问题的答案,按以下格式输出:

$\mathrm{answer}_1$ $\mathrm{answer}_2$ $\ldots$ $\mathrm{answer}_{N-M+1}$

样例

6 4 3
3 1 4 1 5 9

5 6 10

对 $i = 1$,把 $A_i, A_{i+1}, A_{i+2}, A_{i+3}$ 按升序排序得到 $1, 1, 3, 4$,前三个值的和是 $5$。

对 $i = 2$,把 $A_i, A_{i+1}, A_{i+2}, A_{i+3}$ 按升序排序得到 $1, 1, 4, 5$,前三个值的和是 $6$。

对 $i = 3$,把 $A_i, A_{i+1}, A_{i+2}, A_{i+3}$ 按升序排序得到 $1, 4, 5, 9$,前三个值的和是 $10$。

10 6 3
12 2 17 11 19 8 4 3 6 20

21 14 15 13 13

数据范围

• $1 \le K \le M \le N \le 2 \times 10^5$
• $1 \le A_i \le 10^9$
• 输入中的所有值均为整数。