← 返回题目列表

AtCoder · awc0110_b

B. 花坛维护

中文机器翻译题面 查看原题

分数: 300 分

问题陈述

高桥正在维护一个花坛。花坛包含 N 花排成一排,以及品种 i左数第朵花用整数表示 S_i。相同的整数代表同一品种,不同的整数代表不同的品种。

Takahashi 调用了一个部分,其中 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

高桥决定,对于每一朵花,如果存在至少一个包含该花的美丽区间,他将保留它;否则,他会将其删除。

也就是说, i如果存在一对,则保留第 朵花 (l, r) 满足上述条件 1 \leq l \leq i \leq r \leq N。没有这样的花 (l, r) 存在已被删除。

将所有要取出的花朵取出后,确定剩余花朵的品种顺序,按原来的顺序列出。有可能所有的花都被移除而没有留下。

约束

  • 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
  • 第一行包含鲜花数量 N 和最小长度 K 需要一个漂亮的间隔,用空格分隔。
  • 第二行包含整数 每张卡片上写有 S_1, S_2, \ldots, S_N 代表每朵花的品种,以空格分隔。

输出

将要取出的花去掉后剩余的花的品种,按原来的顺序输出,用空格分隔,单行。应输出尾随换行符。如果没有花剩余,则输出空行(仅换行)。


示例输入 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