一个长度为 的好友列表，自上而下依次是 ，你依次收到了 条消息，第 条消息是 发来的，这时 会跳到会话列表的最上面，其它的按原顺序顺延，求 每个好友最靠上的位置和最靠下的位置。
Polycarp is a frequent user of the very popular messenger. He's chatting with his friends all the time. He has friends, numbered from to .
Recall that a permutation of size is an array of size such that each integer from to occurs exactly once in this array.
So his recent chat list can be represented with a permutation of size . is the most recent friend Polycarp talked to, is the second most recent and so on.
Initially, Polycarp's recent chat list looks like 1, 2, \dots, n (in other words, it is an identity permutation).
After that he receives messages, the -th message comes from the friend . And that causes friend to move to the first position in a permutation, shifting everyone between the first position and the current position of by . Note that if the friend is in the first position already then nothing happens.
For example, let the recent chat list be :
For each friend consider all position he has been at in the beginning and after receiving each message. Polycarp wants to know what were the minimum and the maximum positions.
The first line contains two integers and ( ) — the number of Polycarp's friends and the number of received messages, respectively.
The second line contains integers ( ) — the descriptions of the received messages.
Print pairs of integers. For each friend output the minimum and the maximum positions he has been in the beginning and after receiving each message.
5 4 3 5 1 4
1 3 2 5 1 4 1 5 1 5
4 3 1 2 4
1 3 1 2 3 4 1 4
In the first example, Polycarp's recent chat list looks like this:
So, for example, the positions of the friend are , respectively. Out of these is the minimum one and is the maximum one. Thus, the answer for the friend is a pair .
In the second example, Polycarp's recent chat list looks like this: