Berstagram

题意翻译

**题意简述** 给定两个序列 $a=[a_1,a_2,\dots,a_m]$ 和 $b=[b_1,b_2,\dots,b_n]$，其中 $b_i$ 的初始值为 $i$，$a_i$ 的初始值将由键盘读入。对于每个 $a_i$，若 $b_j=a_i$，则将 $b_j$ 与 $b_{j-1}$ 的值调换（若 $j=1$，则序列不变）。 **输入格式** 第一行两个整数 $n$ 和 $m$，意义如上所述。 第二行包含 $m$ 个整数 $a_i$（$1\le i\le m$），表示序列 $a$。 **输出格式** 输出共 $n$ 行，每行包含两个整数。第 $i$ 行的两个数分别表示数字 $i$ 在序列 $b$ 中出现过的所有位置中最靠前的一个与最靠后的一个。 **样例 $1$ 说明** 序列 $b$ 经过每一次操作后的变化： 初始：$[1,2,3]$； 第一次操作后：$[1,3,2]$； 第二次操作后：$[1,2,3]$； 第三次操作后：$[1,2,3]$； 第四次操作后：$[1,3,2]$； 第五次操作后：$[3,1,2]$。 当中，$1$ 出现过的位置有 $1$ 和 $2$，最靠前的是 $1$，最靠后的是 $2$；$2$出现过的位置有 $2$ 和 $3$，最靠前的是 $2$，最靠后的是 $3$；$3$出现过的位置有 $1$，$2$ 和 $3$，最靠前的是 $1$，最靠后的是 $3$。

题目描述

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".

输入输出格式

输入格式

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.

输出格式

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).

输入输出样例

输入样例 #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