102343: [AtCoder]ABC234 D - Prefix K-th Max

Problem Statement

Given are a permutation $P=(P_1,P_2,\ldots,P_N)$ of $(1,2,\ldots,N)$ and a positive integer $K$.

For each $i=K,K+1,\ldots,N$, find the following.

• The $K$-th greatest value among the first $i$ terms of $P$.

Constraints

• $1 \leq K \leq N \leq 5 \times 10^5$
• $(P_1,P_2,\ldots,P_N)$ is a permutation of $(1,2,\ldots,N)$.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

For each $i=K, K+1, \ldots, N$, in this order, print the specified value in Problem Statement, separated by newlines.

Sample Input 1

3 2
1 2 3

Sample Output 1

1
2

• The $(K=)$ $2$-nd greatest value among the first $2$ terms of $P$, $(P_1,P_2)=(1,2)$, is $1$.
• The $(K=)$ $2$-nd greatest value among the first $3$ terms of $P$, $(P_1,P_2,P_3)=(1,2,3)$, is $2$.

Sample Input 2

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

Sample Output 2

2
3
3
5
6
7
7

问题描述

给定一个排列$P=(P_1,P_2,\ldots,P_N)$和一个正整数$K$。

对每个$i=K,K+1,\ldots,N$，找出以下内容。

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

约束条件

• $1 \leq K \leq N \leq 5 \times 10^5$
• $(P_1,P_2,\ldots,P_N)$是$(1,2,\ldots,N)$的一个排列。
• 输入中的所有值都是整数。

输入

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

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

输出

按照顺序，对每个$i=K, K+1, \ldots, N$，在其间打印问题描述中指定的值，用换行符分隔。

样例输入1

3 2
1 2 3

样例输出1

1
2

• 在$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$。

样例输入2

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

样例输出2

2
3
3
5
6
7
7