Độ sâu các nút của cây tìm kiếm nhị phân


Submit solution

Points: 4
Time limit: 1.0s
Memory limit: 977M

Author:
Problem type

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

Cây Tìm kiếm nhị phân

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

  1. Nếu trong cây có rồi thì không bổ sung

  2. 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<=n<=10^4)\) là số phần tử của dãy

Dòng tiếp theo là n số nguyên dương \(a_!, a_2, ... a_n\) có giá trị không vượt quá \(10^4\)

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
tichpx

Comments

There are no comments at the moment.