← 返回题目列表

AtCoder · joig2026final_i

I. 奶酪和老鼠

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

配点 : 100 点

問題文

有一个洞穴,里面住着一只老鼠,在洞穴的前面。 N 奶酪排成一排。 从专栏的开头 i 番目 (1 \leqq i \leqq N)尺寸是 您也可以写 i 是。

洞穴里有一只老鼠。 M 住在那里, 它们的编号最大为1 减去 M 。 老鼠 j (1 \leqq j \leqq M)的大小为 我更喜欢 A_j 及以上的奶酪。 在这里,A_1 < A_2 < \cdots < A_M 满意。

老鼠现在 N 每天执行以下一系列操作。 按照

  1. j = 1, 2, \dots, M 的顺序执行以下操作。
    • 老鼠 如果该行中有 j 喜欢的奶酪,请选择最接近开头的奶酪并与领先的奶酪交换位置。在这里,如果所选奶酪位于开头或者所需奶酪不存在,则不执行任何操作。
  2. 从行中取出行首的奶酪并将其拉入洞穴。

给定有关奶酪、小鼠数量以及小鼠偏好的信息,N 编写一个程序来查找每天可以拉入洞穴的奶酪的大小。


入力

输入是按以下格式从标准输入给出的。

N M
A_1 A_2 \cdots A_{M}

出力

到标准输出 输出 N 输出一行。

k 行目 (1 \leqq k \leqq N)有k 打印当天可以拉入洞穴的奶酪的大小。


制約

  • 1 \leqq M \leqq N \leqq 300\,000.
  • 1 \leqq A_j \leqq N (1 \leqq j \leqq M).
  • A_1 < A_2 < \cdots < A_M.
  • 所有输入值都是整数。

小課題

  1. (11 点) N \leqq 300.
  2. (16 点) N \leqq 5\,000.
  3. (35 点) M = 1.
  4. (38 点)没有额外的限制。

入力例 1

5 2
3 4

出力例 1

4
5
3
2
1

下面,奶酪栏的内容被表示为从头开始按大小顺序排列的数字序列。最初,这些列是 (1,2,3,4,5) 是。 5 白天大鼠的行为进展如下。

  • 老鼠 如果该行中有 1 是尺寸 选择 3 奶酪,该列为 它变成 (3,2,1,4,5) 。老鼠 它变成 2 是尺寸 选择 4 奶酪,该列为 它变成 (4,2,1,3,5) 。最后是尺寸 4 奶酪已从该行中移除,并且该行已 (2,1,3,5) 。
  • 老鼠 如果该行中有 1 是尺寸 选择 3 奶酪,该列为 它变成 (3,1,2,5) 。老鼠 它变成 2 是尺寸 选择 5 奶酪,该列为 它变成 (5,1,2,3) 。最后是尺寸 5 奶酪已从该行中移除,并且该行已 (1,2,3) 。
  • 老鼠 如果该行中有 1 是尺寸 选择 3 奶酪,该列为 它变成 (3,2,1) 。老鼠 它变成 2 什么也不做。最后是尺寸 3 奶酪已从该行中移除,并且该行已 (2,1) 。
  • 两只鼠标都没有执行任何操作。尺寸 2 奶酪已从该行中移除,并且该行已 (1) 。
  • 两只鼠标都没有执行任何操作。尺寸 1 奶酪从该行中移除,使该行为空。

此输入示例是一个小作业。 1,2,4 满足约束。


入力例 2

3 1
2

出力例 2

2
3
1

此输入示例满足所有子任务约束。