OJ现已增加邮箱找回密码功能，还没有绑定邮箱的同学们请抓紧时间，以免密码丢失无法找回
题目描述
众所周知小Jin是个社交达人，每天都有很多同学找他聊天。
假设他有n个好友，由于每个好友都给他发过消息，所以消息列表里共有n条消息，初始状态好友1位于1号位置，好友2位于2号位置...
当好友x给小Jin发消息时，x的消息框就会被排到第一个，同时其余的好友消息框都会往下顺延（序号增大）。小G现在想知道，发完m条消息的过程中，每个好友的消息框所处的最大和最小位置分别是多少？
输入
第一行输入两个整数n，m（1 ≤ n，m ≤ 1e5），分别表示好友总数和发消息总数。接下来一行输入m个整数ai（1 ≤ ai ≤ n），表示ai发了一条消息，ai按照时间顺序给出。
输出
输出n行，每行两个整数，分别表示第i个人消息框的最小位置和最大位置。
样例输入 Copy
4 3
1 2 4
样例输出 Copy
1 3
1 2
3 4
1 4
提示
初始好友1，2，3，4分别位于1，2，3，4位置，当好友1发消息时，消息列表不动。好友2发消息时，消息框变为2，1，3，4。好友4发消息时，消息框变为4，2，1，3。