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