B - 特別賞 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君はプログラミングコンテストを行い、N 人の人が参加しました。賞品がないと物足りないのではないかと思った高橋君は「i 位以上の人のうち、K 番目に若い人」に特別賞を出すことにしました。参加者全員の年齢は分かっています。K の値はもう既に決めているのですが、i の値はまだ決めていません。i の値を決めるために高橋君は、K 以上 N 以下の整数 i それぞれについて誰が特別賞を取ることが出来るのかを計算してみることにしました。

入力

入力は以下の形式で標準入力から与えられる。

N K
X_1 X_2 ... X_N
  • 1 行目には、コンテストに参加した人数を表した整数 N (1 ≦ N ≦ 100,000) と、整数 K (1 ≦ K ≦ N) が空白区切りで与えられる。
  • 2 行目には、参加者の年齢の情報を表す N 個の整数が空白区切りで与えられる。このうち i 番目の整数 X_i (1 ≦ X_i ≦ N) は、順位が i 位の参加者の年齢が全参加者のうち X_i 番目に若いことを表す。ただし、p \neq q のとき X_p \neq X_q であることが保証される。

部分点

この問題には部分点が設定されている。

  • N ≦ 1000 を満たすテストケースすべてに正解した場合は 40 点が与えられる。

出力

N-K+1 行に出力せよ。そのうち i 行目には、「i+K-1 位以上の人のうち、K 番目に若い人」の順位を表す 1 つの整数を出力せよ。

入力例1

5 2
4 5 3 1 2

出力例1

2
1
3
5

以下は、出力の各行についての説明です。

  • 1 行目： 2 位以上の人のうち 2 番目に若い人は 2 位の人です。
  • 2 行目： 3 位以上の人のうち 2 番目に若い人は 1 位の人です。
  • 3 行目： 4 位以上の人のうち 2 番目に若い人は 3 位の人です。
  • 4 行目： 5 位以上の人のうち 2 番目に若い人は 5 位の人です。

入力例2

3 1
2 3 1

出力例2

1
1
3