AT_abc234_d [ABC234D] Prefix K-th Max

题目描述

给定一个 $(1,2,\ldots,N)$ 的排列 $P=(P_1,P_2,\ldots,P_N)$，以及一个正整数 $K$。

对于 $i=K,K+1,\ldots,N$，请你求出以下内容：

• 在 $P$ 的前 $i$ 项中，第 $K$ 大的值。

输入格式

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

$N$ $K$ $P_1$ $P_2$ $\ldots$ $P_N$

输出格式

对于 $i=K,K+1,\ldots,N$，按顺序输出题目要求的值，每个值占一行。

输入输出样例 #1

输入 #1

3 2
1 2 3

输出 #1

1
2

输入输出样例 #2

输入 #2

11 5
3 7 2 5 11 6 1 9 8 10 4

输出 #2

2
3
3
5
6
7
7

说明/提示

限制条件

• $1\leq K\leq N\leq 5\times 10^5$
• $(P_1,P_2,\ldots,P_N)$ 是 $(1,2,\ldots,N)$ 的一个排列
• 输入均为整数

样例解释 1

• 在 $P$ 的前 $2$ 项，即 $(P_1,P_2)=(1,2)$ 中，第 $K=2$ 大的值是 $1$。
• 在 $P$ 的前 $3$ 项，即 $(P_1,P_2,P_3)=(1,2,3)$ 中，第 $K=2$ 大的值是 $2$。

由 ChatGPT 4.1 翻译