Cho một dãy số nguyên \(a\) gồm \(2\cdot n\) phần tử, mỗi số từ \(1\) đến \(n\) xuất hiện chính xác \(2\) lần. Chúng ta nói rằng một đoạn \(y\) giao nhau với đoạn \(x\) nếu có đúng một vị trí của số \(y\) trên \(a\) nằm giữa 2 vị trí của số \(x\) trên \(a\).

Yêu cầu

• Với mỗi đoạn \(i\), đếm xem có bao nhiêu đoạn giao với nó.

Input

• Dòng đầu chứa một số nguyên dương \(n\).
• Dòng 2 chứa \(2\cdot n\) số nguyên. Mỗi số từ \(1\) đến \(n\) xuất hiện chính xác 2 lần.

Output

• In ra \(n\) số trên một dòng, số thứ \(i\) là kết quả của đoạn \(i\).

Constraints

• \(1\le n\le 250000\)

Example