Sắp xếp là một trong những bài toán phổ biến nhất trong khoa học máy tính. An vừa được giới thiệu các thuật toán sắp xếp và biết rằng thuật toán sắp xếp nhanh (Quick Sort) có độ phức tạp trung bình là ~O(N \times logN)~. Tuy nhiên An vẫn muốn sáng tạo một thuật toán sắp xếp mới và xem thử liệu nó có tốt hơn Quick Sort. Xét một mảng ~N~ số nguyên, mỗi phần tử có giá trị từ ~1~ đến ~N~ và mỗi giá trị chỉ xuất hiện một lần trong mảng. Thuật toán này sẽ sắp xếp mảng trên trong ~N~ bước như sau:

• Bước 1: phần tử có giá trị 1 sẽ được chuyển đến vị trí 1 bằng cách liên tiếp hoán đổi vị trí với phần tử liền kề với nó.
• Bước 2: phần tử có giá trị ~N~ sẽ được chuyển đến vị trí ~N~ bằng cách như bước 1.
• Bước 3: phần tử có giá trị 2 sẽ được chuyển đến vị trí 2 bằng cách tương tự.
• Bước 4: phần tử có giá trị ~N - 1~ sẽ được chuyển đến vị trí ~N - 1~ bằng cách tương tự.
• Và cứ thế tiếp tục đến bước ~N~.

Tổng quát hơn, ở bước lẻ, An sẽ chọn phần tử có giá trị nhỏ nhất chưa được sắp xếp và di chuyển phần tử này đến vị trí đúng của nó. Ở bước chẵn An sẽ chọn phần tử có giá trị lớn nhất chưa được sắp xếp và di chuyển phần tử này đến vị trí đúng của nó.

Yêu cầu: Viết chương trình cho biết số lần hoán đổi vị trí các phần tử tại mỗi bước của thuật toán.

Input

• Dòng đầu tiên chứa một số nguyên ~N~ cho biết số lượng phần tử của mảng.
• Trong ~N~ dòng tiếp theo, dòng thứ ~i~ chứa một số nguyên ~a_i~ (~1 \le a_i \le N~) cho biết giá trị của phần tử thứ ~i~ trong mảng. Các giá trị ~a_i~ không lặp lại.

Output

• Gồm ~N~ số nguyên, số thứ ~i~ cho biết số lần hoán đổi vị trí các phần tử ở bước thứ ~i~ của thuật toán. Mỗi số ghi trên một dòng.