← 返回题目列表

Codeforces · 1288/E

E. 信使模拟器

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

Polycarp 是这款非常受欢迎的即时通讯工具的频繁用户。他一直在和他的朋友聊天。他有 $$$n$$$ 个朋友,编号从 $$$1$$$ 到 $$$n$$$。

回想一下,大小 $$$n$$$ 的排列是大小为 $$$n$$$ 的数组,使得从 $$$1$$$ 到 $$$n$$$ 的每个整数在此数组中恰好出现一次。

所以他最近的聊天列表可以用大小为 $$$n$$$ 的排列 $$$p$$$ 来表示。 $$$p_1$$$ 是最近与波利卡普交谈过的朋友,$$$p_2$$$ 是第二个最近的朋友,依此类推。

最初,Polycarp 最近的聊天列表 $$$p$$$ 看起来像 $$$1, 2, \dots, n$$$ (换句话说,它是一个身份排列)。

收到$$$m$$$消息后,第$$$j$$$消息来自好友$$$a_j$$$。这会导致朋友 $$$a_j$$$ 移动到排列中的第一个位置,将每个人在 $$$a_j$$$ 的第一个位置和当前位置之间移动 $$$1$$$。请注意,如果朋友 ​​$$$a_j$$$ 已经处于第一个位置,那么什么也不会发生。

例如,设最近聊天列表为$$$p = [4, 1, 5, 3, 2]$$$:

- 如果他收到好友 $$$3$$$ 的消息,则 $$$p$$$ 变为 $$$[3, 4, 1, 5, 2]$$$;
- 如果他收到好友 $$$4$$$ 的消息,则 $$$p$$$ 不会改变 $$$[4, 1, 5, 3, 2]$$$;
- 如果他收到朋友 $$$2$$$ 的消息,那么 $$$p$$$ 会变成 $$$[2, 4, 1, 5, 3]$$$。

对于每个朋友,请考虑他在开始和收到每条消息后所处的所有位置。坡旅甲想知道最小和最大位置是多少。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 3 \cdot 10^5$$$) — 分别是波利卡普的好友数量和收到的消息数量。

第二行包含 $$$m$$$ 整数 $$$a_1, a_2, \dots, a_m$$$ ($$$1 \le a_i \le n$$$) — 接收到的消息的描述。

输出

打印 $$$n$$$ 整数对。对于每个朋友,输出他在开始和收到每条消息后的最小和最大位置。

示例

输入 #1

5 4
3 5 1 4

输出 #1

1 3
2 5
1 4
1 5
1 5

输入 #2

4 3
1 2 4

输出 #2

1 3
1 2
3 4
1 4

注意

在第一个示例中,Polycarp 最近的聊天列表如下所示:

- $$$[1, 2, 3, 4, 5]$$$
- $$$[3, 1, 2, 4, 5]$$$
- $$$[5, 3, 1, 2, 4]$$$
- $$$[1, 5, 3, 2, 4]$$$
- $$$[4, 1, 5, 3, 2]$$$

因此,例如,朋友 $$$2$$$ 的位置分别为 $$$2, 3, 4, 4, 5$$$。其中 $$$2$$$ 是最小的,$$$5$$$ 是最大的。因此,朋友 $$$2$$$ 的答案是一对 $$$(2, 5)$$$。

在第二个示例中,Polycarp 最近的聊天列表如下所示:

- $$$[1, 2, 3, 4]$$$
- $$$[1, 2, 3, 4]$$$
- $$$[2, 1, 3, 4]$$$
- $$$[4, 2, 1, 3]$$$