分数: 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