B - Flower Bed Maintenance Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君は花壇の整備を行っています。花壇には N 本の花が一列に並んでおり、左から i 番目の花の品種は整数 S_i で表されます。同じ整数は同じ品種を、異なる整数は異なる品種を表します。

高橋君は、同じ品種の花が K 本以上連続して並んでいる部分を「見栄えの良い区間」と呼んでいます。

より正確には、整数の組 (l, r) が以下のすべてを満たすとき、左から l 番目の花から r 番目の花までの連続する並びを見栄えの良い区間と呼びます。

  • 1 \leq l \leq r \leq N
  • S_l = S_{l+1} = \cdots = S_r
  • r - l + 1 \geq K

高橋君は、各花について、その花を含む見栄えの良い区間が少なくとも1つ存在するならばその花を残し、そのような区間が1つも存在しないならばその花を抜き取ることにしました。

すなわち、i 番目の花を残すのは、1 \leq l \leq i \leq r \leq N かつ上の条件を満たす組 (l, r) が存在するときです。そのような (l, r) が存在しない花は抜き取ります。

抜き取る花をすべて除去した後、残った花の品種を元の並び順を保ったまま並べた列を求めてください。すべての花が抜き取られ、1本も残らない場合もあり得ます。

制約

  • 1 \leq N \leq 10^6
  • 1 \leq K \leq N
  • 1 \leq S_i \leq 10^9 (1 \leq i \leq N)
  • 入力はすべて整数である。

入力

N K
S_1 S_2 \ldots S_N
  • 1 行目には、花の本数 N と、見栄えの良い区間に必要な最小の長さ K が、スペース区切りで与えられる。
  • 2 行目には、各花の品種を表す整数 S_1, S_2, \ldots, S_N が、スペース区切りで与えられる。

出力

抜き取る花を除去した後に残った花の品種を、元の並び順を保ったままスペース区切りで 1 行で出力せよ。末尾には改行を出力すること。花が1本も残らない場合は、空の行（改行のみ）を出力せよ。

入力例 1

10 3
1 2 2 2 3 1 1 1 1 2

出力例 1

2 2 2 1 1 1 1

入力例 2

5 3
1 2 1 2 1

出力例 2

入力例 3

15 2
3 3 1 4 4 4 2 1 1 5 5 5 5 3 2

出力例 3

3 3 4 4 4 1 1 5 5 5 5

入力例 4

20 4
1 1 1 1 2 2 2 3 3 3 3 3 1 2 2 2 2 2 1 1

出力例 4

1 1 1 1 3 3 3 3 3 2 2 2 2 2

入力例 5

1 1
42

出力例 5

42

Score : 300 pts

Problem Statement

Takahashi is maintaining a flower bed. The flower bed contains N flowers arranged in a row, and the variety of the i-th flower from the left is represented by an integer S_i. The same integer represents the same variety, and different integers represent different varieties.

Takahashi calls a section where K or more consecutive flowers of the same variety are lined up a "beautiful interval."

More precisely, a continuous sequence from the l-th flower to the r-th flower from the left is called a beautiful interval when the pair of integers (l, r) satisfies all of the following conditions:

  • 1 \leq l \leq r \leq N
  • S_l = S_{l+1} = \cdots = S_r
  • r - l + 1 \geq K

Takahashi decided that for each flower, if there exists at least one beautiful interval containing that flower, he will keep it; otherwise, he will remove it.

That is, the i-th flower is kept if there exists a pair (l, r) satisfying the above conditions with 1 \leq l \leq i \leq r \leq N. Flowers for which no such (l, r) exists are removed.

After removing all the flowers to be taken out, determine the sequence of varieties of the remaining flowers, listed in their original order. It is possible that all flowers are removed and none remain.

Constraints

  • 1 \leq N \leq 10^6
  • 1 \leq K \leq N
  • 1 \leq S_i \leq 10^9 (1 \leq i \leq N)
  • All input values are integers.

Input

N K
S_1 S_2 \ldots S_N
  • The first line contains the number of flowers N and the minimum length K required for a beautiful interval, separated by a space.
  • The second line contains the integers S_1, S_2, \ldots, S_N representing the variety of each flower, separated by spaces.

Output

Output the varieties of the remaining flowers after removing the flowers to be taken out, in their original order, separated by spaces, on a single line. A trailing newline should be output. If no flowers remain, output an empty line (only a newline).

Sample Input 1

10 3
1 2 2 2 3 1 1 1 1 2

Sample Output 1

2 2 2 1 1 1 1

Sample Input 2

5 3
1 2 1 2 1

Sample Output 2

Sample Input 3

15 2
3 3 1 4 4 4 2 1 1 5 5 5 5 3 2

Sample Output 3

3 3 4 4 4 1 1 5 5 5 5

Sample Input 4

20 4
1 1 1 1 2 2 2 3 3 3 3 3 1 2 2 2 2 2 1 1

Sample Output 4

1 1 1 1 3 3 3 3 3 2 2 2 2 2

Sample Input 5

1 1
42

Sample Output 5

42