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