GHI CHÚ: ĐÂY LÀ ĐỀ ĐƯỢC VIẾT LẠI BỞI NQSON. BẢN DỄ HƠN THAM KHẢO TẠI ĐÂY

Tichpx dạy về Cấu trúc dữ liệu cây tìm kiếm nhị phân quản lý ở mỗi nút là một số nguyên.

Thao tác bổ sung một giá trị vào cây được thực hiện như sau:

• Nếu trong cây có rồi thì không bổ sung.
• Nếu trong cây chưa có thì bổ sung bằng cách duyệt từ gốc nếu nhỏ hơn nút đang xét thì bổ sung sang trái, nếu lớn hơn thì bổ sung sang phải cứ như thế đến nút trống thì chèn vào.

Độ sâu của một nút là số bước đi từ gốc đến nó, tất nhiên độ sâu của nút gốc sẽ là \(0\).

Nhiệm vụ của bạn là thêm từ từ các phần tử của một dãy vào một cây tìm kiếm nhị phân sau khi thêm xong toàn bộ các phần tử bạn hãy duyệt cây theo trung thứ tự để xuất ra các nút tăng dần từ nhỏ đến lớn mỗi nút và độ sâu của nút đó.

Input

Dòng đầu là số nguyên dương \(n\) \((1 \le n \le 10^5)\) là số phần tử của dãy.

Dòng tiếp theo chứa \(n\) số nguyên dương \(a_1, a_2, ... a_n\) có giá trị không vượt quá \(10^9\).

Output

Xuất ra từng dòng là giá trị từng nút từ bé đến lớn và độ sâu tương ứng của nút đó.

Ví dụ

Input:

10
34 66 17 50 71 17 94 25 50 68

Output:

17 1
25 2
34 0
50 2
66 1
68 3
71 2
94 3