CF1250A.Berstagram

Polycarp recently signed up to a new social network Berstagram. He immediately published $n$ posts there. He assigned numbers from $1$ to $n$ to all posts and published them one by one. So, just after publishing Polycarp's news feed contained posts from $1$ to $n$ — the highest post had number $1$, the next one had number $2$, ..., the lowest post had number $n$.

After that he wrote down all likes from his friends. Likes were coming consecutively from the $1$-st one till the $m$-th one. You are given a sequence $a_1, a_2, \dots, a_m$ ($1 \le a_j \le n$), where $a_j$ is the post that received the $j$-th like.

News feed in Berstagram works in the following manner. Let's assume the $j$-th like was given to post $a_j$. If this post is not the highest (first) one then it changes its position with the one above. If $a_j$ is the highest post nothing changes.

For example, if $n=3$, $m=5$ and $a=[3,2,1,3,3]$, then Polycarp's news feed had the following states:

• before the first like: $[1, 2, 3]$;
• after the first like: $[1, 3, 2]$;
• after the second like: $[1, 2, 3]$;
• after the third like: $[1, 2, 3]$;
• after the fourth like: $[1, 3, 2]$;
• after the fifth like: $[3, 1, 2]$.

Polycarp wants to know the highest (minimum) and the lowest (maximum) positions for each post. Polycarp considers all moments of time, including the moment "before all likes".

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 的信息流经历了如下状态变化：

• 在第一个点赞之前：$[1, 2, 3]$；
• 第一个点赞之后：$[1, 3, 2]$；
• 第二个点赞之后：$[1, 2, 3]$；
• 第三个点赞之后：$[1, 2, 3]$；
• 第四个点赞之后：$[1, 3, 2]$；
• 第五个点赞之后：$[3, 1, 2]$。

Polycarp 想要知道每篇帖子在整个过程中所达到的最高位置（即最小的排名数值） 和 最低位置（即最大的排名数值）。Polycarp 考虑所有时刻，包括“所有点赞发生之前”这一初始时刻。

The first line contains two integer numbers $n$ and $m$ ($1 \le n \le 10^5$, $1 \le m \le 4 \cdot10^5$) — number of posts and number of likes.

The second line contains integers $a_1, a_2, \dots, a_m$ ($1 \le a_j \le n$), where $a_j$ is the post that received the $j$-th like.

第一行包含两个整数 $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$ 个点赞的帖子编号。

Print $n$ pairs of integer numbers. The $i$-th line should contain the highest (minimum) and the lowest (maximum) positions of the $i$-th post. You should take into account positions at all moments of time: before all likes, after each like and after all likes. Positions are numbered from $1$ (highest) to $n$ (lowest).

输出 $n$ 对整数。第 $i$ 行应包含第 $i$ 个帖子的最高（最小）位置和最低（最大）位置。你需要考虑所有时刻的位置：所有点赞之前、每次点赞之后，以及所有点赞之后。位置编号从 $1$（最高）到 $n$（最低）。