← 返回题目列表

Codeforces · 1250/A

A. 伯斯塔格拉姆

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

Polycarp 最近注册了一个新的社交网络 Berstagram。他立即在那里发布了 $$$n$$$ 帖子。他为所有帖子分配了从$$$1$$$到$$$n$$$的编号,并一一发布。因此,就在发布 Polycarp 的新闻提要后,包含从 $$$1$$$ 到 $$$n$$$ 的帖子 — 最高的帖子编号为 $$$1$$$,下一个帖子的编号为 $$$2$$$,...,最低的帖子编号为 $$$n$$$。

之后他写下了所有朋友的点赞。从第 $$$1$$$ 到第 $$$m$$$ 连续点赞。给定一个序列 $$$a_1, a_2, \dots, a_m$$$ ($$$1 \le a_j \le n$$$),其中 $$$a_j$$$ 是收到第 $$$j$$$ 个赞的帖子。

Berstagram 中的新闻源按以下方式工作。让我们假设第 $$$j$$$ 个赞是用来发布 $$$a_j$$$ 的。如果这个帖子不是最高的(第一个)帖子,那么它会与上面的帖子改变位置。如果 $$$a_j$$$ 是最高的帖子,则不会发生任何变化。

例如,如果 $$$n=3$$$、$$$m=5$$$ 且 $$$a=[3,2,1,3,3]$$$,则 Polycarp 的新闻提要具有以下状态:

- 第一个 like 之前:$$$[1, 2, 3]$$$;
- 第一个像之后:$$$[1, 3, 2]$$$;
- 第二个之后:$$$[1, 2, 3]$$$;
- 第三个之后:$$$[1, 2, 3]$$$;
- 第四个之后:$$$[1, 3, 2]$$$;
- 在第五个之后:$$$[3, 1, 2]$$$。

Polycarp 想知道每个职位的最高(最低)和最低(最高)职位。波利卡普考虑了所有时刻,包括“所有喜欢之前”的时刻。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le m \le 4 \cdot10^5$$$) — 帖子数和点赞数。

第二行包含整数 $$$a_1, a_2, \dots, a_m$$$ ($$$1 \le a_j \le n$$$),其中 $$$a_j$$$ 是收到第 $$$j$$$ 个赞的帖子。

输出

打印 $$$n$$$ 整数对。第 $$$i$$$ 行应包含第 $$$i$$$ 帖子的最高(最小)和最低(最大)位置。您应该考虑所有时刻的位置:在所有点赞之前、每次点赞之后以及在所有点赞之后。职位编号从$$$1$$$(最高)到$$$n$$$(最低)。

示例

输入 #1

3 5
3 2 1 3 3

输出 #1

1 2
2 3
1 3

输入 #2

10 6
7 3 5 7 3 6

输出 #2

1 2
2 3
1 3
4 7
4 5
6 7
5 7
8 8
9 9
10 10