Cây nhị phân gồm \(n\) nút ứng với \(n\) khóa \(k_1, k_2, ..., k_n\) sao cho với mỗi nút \(x\):

• Mọi khóa trên cây con trái đều nhỏ hơn khóa trên nút \(x\).
• Mọi khóa trên cây con phải đều lớn hơn khóa trên nút \(x\).

được gọi là cây tìm kiếm nhị phân.

Cho dãy \(A\) gồm \(n\) phần tử nguyên dương không lớn hơn \(n\) và đôi một phân biệt, hãy dựng cây tìm kiếm nhị phân từ dãy \(A\) bằng việc chèn lần lượt chèn các phần tử của dãy \(A\) vào cây theo thứ tự trong dãy.

Để chèn phần tử có giá trị \(x\) vào trong cây, ta làm như sau: Nếu cây không có nút gốc, ta đặt nút có khóa là \(x\) làm nút gốc. Nếu cây có nút gốc, ta xét nút gốc rồi di chuyển như sau:

• Nếu \(x\) nhỏ hơn khóa của nút đang xét, ta di chuyển sang nút con trái của nút đang xét, nếu nút đó không tồn tại, ta tạo một nút có khóa là \(x\) rồi đặt nút đó làm nút con trái của nút đang xét và kết thúc.
• Nếu \(x\) lớn hơn khóa của nút đang xét, ta di chuyển sang nút con phải của nút đang xét, nếu nút đó không tồn tại, ta tạo một nút có khóa là \(x\) rồi đặt nút đó làm nút con phải của nút đang xét và kết thúc.
• Tiếp tục di chuyển và xét các nút cho đến khi ta không thể di chuyển được nữa.

Do việc in cấu trúc của một cây nhị phân quá phức tạp, với mỗi lần chèn một phần tử trong dãy \(A\), chương trình của bạn chỉ cần cộng số nút ta cần xét để chèn phần tử đó vào biến đếm \(R\) rồi in giá trị của \(R\). Ban đầu, biến đếm \(R\) có giá trị là \(0\).

Input

• Dòng thứ nhất một số nguyên dương \(n\) (\(1 \lt n \lt 3 \leq 10^5\)) là số lượng phần tử của dãy \(A\).
• \(n\) dòng tiếp theo, dòng thứ \(i\) gồm một số nguyên dương \(A_i\) (\(1 < A_i < n\)) là phần tử thứ \(i\) của dãy \(A\) Dữ liệu vào đảm bảo không có hai phần tử nào trong dãy \(A\) bằng nhau.

Output

• Gồm \(n\) dòng, dòng thứ \(i\) gồm một số nguyên là giá trị của biến đếm \(R\) sau khi chèn phần tử thứ \(i\) của dãy \(A\).

Example

8
3
5
1
6
8
7
2
4 

0
1
2
4
7
11
13
15