Given an array of $2n$ numbers, each number from $1$ to $n$ in it occurs exactly twice. We say that the segment $y$ is nested inside the segment $x$ if both occurrences of the number $y$ are between the occurrences of the number $x$. Find for each segment $i$ how many segments that are nested inside 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 nested inside the segment $i$.