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\) nằm trong đoạn \(x\) nếu cả \(2\) 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 nằm trong 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