Cây tìm kiếm nhị phân - Bộ đếm độ sâu (Binary Search Tree)

Nguồn: Kattis

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho một hoán vị của các số từ $1$ đến $n$. Dùng các số theo đúng thứ tự input để dựng một cây tìm kiếm nhị phân: số đầu tiên trở thành gốc; với mỗi số tiếp theo, bắt đầu từ gốc, đi sang trái nếu số mới nhỏ hơn khóa hiện tại và sang phải nếu lớn hơn, cho đến khi gặp vị trí con rỗng rồi tạo nút mới tại đó.

Độ sâu của gốc bằng $0$. Độ sâu của một nút khác là số cạnh trên đường đi từ gốc đến nút đó.

Có một bộ đếm $C$, ban đầu bằng $0$. Sau khi chèn mỗi phần tử, cộng độ sâu của nút vừa được chèn vào $C$, rồi in giá trị hiện tại của $C$.

Phần tử đầu tiên là gốc nên có độ sâu $0$ và giá trị đầu tiên được in cũng là $0$.

Input

Dòng đầu chứa số nguyên $n$.

$n$ dòng tiếp theo lần lượt chứa $a_1,a_2,\ldots,a_n$. Dãy này là một hoán vị của $1,2,\ldots,n$.

Output

In đúng $n$ dòng. Dòng thứ $i$ là giá trị của bộ đếm $C$ ngay sau khi chèn $a_i$.

Subtask

Subtask 1 (20 điểm): $1\le n\le 20$.

Subtask 2 (30 điểm): $1\le n\le 5000$.

Subtask 3 (50 điểm): $1\le n\le 300000$.

Trong tất cả các subtask, $a_1,a_2,\ldots,a_n$ là một hoán vị của các số nguyên từ $1$ đến $n$.

Ví dụ

Input

8
3
5
1
6
8
7
2
4

Output

0
1
2
4
7
11
13
15

Giải thích

Các nút mới được chèn lần lượt có độ sâu $0,1,1,2,3,4,2,2$.

Bộ đếm bắt đầu từ $0$. Cộng dồn các độ sâu trên sau từng lần chèn thu được $0,1,2,4,7,11,13,15$, đúng bằng tám dòng output.