AT_arc028_2.[ARC028B] 特別賞

高桥君举办了一场编程竞赛，共有 $N$ 人参加。他觉得如果没有奖品会有些无聊，于是决定给“在第 $i$ 名及以上的选手中，第 $K$ 年轻的人”颁发特别奖。所有参赛者的年龄信息已知。$K$ 的值已经确定，但 $i$ 的值还未决定。为了决定 $i$ 的值，高桥君想要计算对于每一个 $K \leq i \leq N$ 的整数 $i$，谁能获得特别奖。

已知所有参赛者的年龄。对于每一个 $K$ 到 $N$ 的 $i$，请计算“在第 $i$ 名及以上的选手中，第 $K$ 年轻的人”是第几名。

输入以如下格式从标准输入读入。

$N$ $K$ $X_1$ $X_2$ ... $X_N$

• 第 $1$ 行包含两个用空格分隔的整数 $N\ (1 \leq N \leq 100,000)$ 和 $K\ (1 \leq K \leq N)$，分别表示参赛人数和 $K$ 的值。
• 第 $2$ 行包含 $N$ 个用空格分隔的整数，表示参赛者的年龄信息。其中第 $i$ 个整数 $X_i\ (1 \leq X_i \leq N)$ 表示排名第 $i$ 的参赛者是所有参赛者中第 $X_i$ 年轻的人。保证对于 $p \neq q$，有 $X_p \neq X_q$。

输出 $N-K+1$ 行。第 $i$ 行输出一个整数，表示“在第 $i+K-1$ 名及以上的选手中，第 $K$ 年轻的人”的名次。

部分分

本题设有部分分。

• 若能正确解决所有 $N \leq 1000$ 的测试点，可获得 $40$ 分。

样例解释 1

以下是每一行输出的说明。

• 第 $1$ 行：在第 $2$ 名及以上的选手中，第 $2$ 年轻的人是第 $2$ 名的选手。
• 第 $2$ 行：在第 $3$ 名及以上的选手中，第 $2$ 年轻的人是第 $1$ 名的选手。
• 第 $3$ 行：在第 $4$ 名及以上的选手中，第 $2$ 年轻的人是第 $3$ 名的选手。
• 第 $4$ 行：在第 $5$ 名及以上的选手中，第 $2$ 年轻的人是第 $5$ 名的选手。

由 ChatGPT 4.1 翻译