Sắp xếp đồng xu

Có $n$ đồng xu xếp thành một hàng, đánh số từ $1$ đến $n$ từ trái sang phải. Mỗi đồng xu thuộc một trong hai loại: O (đã ngừng lưu hành) hoặc X (còn lưu hành). Hàng được gọi là đã sắp xếp nếu mọi đồng O đứng trước mọi đồng X.

Để sắp xếp, người ta lặp lại một lượt như sau:

1. Duyệt các đồng xu từ trái sang phải.
2. Nếu đồng xu thứ $i$ là X và đồng xu thứ $i+1$ là O thì đổi chỗ hai đồng xu này, rồi tiếp tục duyệt từ vị trí $i+1$ (tức là đồng X vừa được đẩy sang phải có thể tiếp tục bị đổi chỗ trong cùng lượt).

Quá trình dừng lại ngay sau lượt đầu tiên không có phép đổi chỗ nào. Độ khó của hàng là tổng số lượt đã thực hiện, tính cả lượt cuối cùng không đổi chỗ. Ví dụ, một hàng đã sắp xếp có độ khó bằng $1$.

Ban đầu cả $n$ đồng xu đều là O. Sau đó lần lượt $n$ lần, đồng xu ở vị trí $p_i$ được thay bằng đồng X. Hãy tính độ khó của hàng ở trạng thái ban đầu và sau mỗi lần thay.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $n$.
• Dòng thứ hai chứa $n$ số nguyên phân biệt $p_1,p_2,\dots ,p_n$.

Dữ liệu ra

In ra $n+1$ số nguyên $a_0,a_1,\dots ,a_n$ trên một dòng, cách nhau bởi dấu cách, trong đó $a_0$ là độ khó của hàng ban đầu và $a_i$ là độ khó sau lần thay thứ $i$.

Ràng buộc

• $1\le n\le 300000$
• $1\le p_i\le n$, các $p_i$ đôi một phân biệt

Ví dụ