Given an array of $2n$ numbers, each number from $1$ to $n$ in it occurs exactly twice. We say that the segment $y$ intersects the segment $x$ if exactly one occurrence of the number $y$ is between the occurrences of the number $x$. Find for each segment $i$ how many segments there are that intersect with it.

The first line contains the number $n\ (1≤n≤10^5)$. 

The second line contains $2n$ numbers. It is guaranteed that every number from $1$ to $n$ occurs exactly twice.

Print $n$ numbers, the $i$-th number is equal to the number of segments that intersect with the segment $i$.