Berstagram

Trên một mạng xã hội, một người dùng đăng tải $n$ bài viết được đánh số từ $1$ đến $n$. Ngay sau khi đăng, bảng tin có thứ tự từ trên xuống dưới là $1,2,\dots ,n$ — bài có vị trí cao nhất là bài $1$, thấp nhất là bài $n$.

Sau đó, lần lượt có $m$ lượt thích đến. Lượt thích thứ $j$ được dành cho bài $a_j$. Quy tắc cập nhật bảng tin như sau: nếu bài $a_j$ không phải bài đang ở vị trí cao nhất, nó đổi chỗ với bài ngay phía trên. Nếu $a_j$ đã ở vị trí cao nhất thì không có gì thay đổi.

Với mỗi bài $i$, hãy tìm vị trí cao nhất (số nhỏ nhất) và vị trí thấp nhất (số lớn nhất) mà nó từng đạt được. Phải xét tất cả các thời điểm: trước khi có lượt thích nào, sau mỗi lượt thích, và sau lượt thích cuối cùng. Vị trí được đánh số từ $1$ (cao nhất) đến $n$ (thấp nhất).

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• Dòng thứ hai chứa $m$ số nguyên $a_1,a_2,\dots ,a_m$.

Dữ liệu ra

In ra $n$ dòng. Dòng thứ $i$ chứa hai số nguyên: vị trí cao nhất và vị trí thấp nhất mà bài $i$ từng đạt được.

Ràng buộc

• $1\le n\le {10}^5$
• $1\le m\le 4·{10}^5$
• $1\le a_j\le n$

Ví dụ