D - Prefix K-th Max Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

(1,2,\ldots,N) の順列 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

Score : 400 points

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