$N$ balls are lined up in $1$ row. From left to right, they are called Ball $1, 2, \dots, N$. Ball $i$ is painted with color $C_i$.

For each $i = 1, 2, \dots, N$, find the following value:

• The sum of the distances to Ball $i$ over all balls that have the same color as Ball $i$. Here, the distance between Ball $i$ and Ball $j$ is defined as $|i - j|$.

Constraints

• $1 \le N \le 100$.
• $1 \le C_i \le 100$ ($1 \le i \le N$).
• All input values are integers.

Input

The input is given in the following format:

N
C_1 C_2 ... C_N

Output

Output $N$ lines. On the $i$-th line ($1 \le i \le N$), output the sum of the distances to Ball $i$ over all balls that have the same color as Ball $i$.

Do not output anything other than the answer. (Do not output prompt sentences or anything similar.)

Examples

Input 1

4
1 2 1 1

Output 1

5
0
3
4

Note 1

Ball $1$ is painted with color $1$, Ball $2$ with color $2$, Ball $3$ with color $1$, and Ball $4$ with color $1$.

• For $i = 1$, the balls with the same color as Ball $1$ are Balls $1, 3, 4$, and their distances from Ball $1$ are $0, 2, 3$, respectively, so output $0 + 2 + 3 = 5$.
• For $i = 2$, the only ball with the same color as Ball $2$ is Ball $2$, and its distance from Ball $2$ is $0$, so output $0$.
• For $i = 3$, the balls with the same color as Ball $3$ are Balls $1, 3, 4$, and their distances from Ball $3$ are $2, 0, 1$, respectively, so output $2 + 0 + 1 = 3$.
• For $i = 4$, the balls with the same color as Ball $4$ are Balls $1, 3, 4$, and their distances from Ball $4$ are $3, 1, 0$, respectively, so output $3 + 1 + 0 = 4$.

Input 2

1
100

Output 2

0

Note 2

Ball $1$ is painted with color $100$.

• For $i = 1$, the only ball with the same color as Ball $1$ is Ball $1$, and its distance from Ball $1$ is $0$, so output $0$.

Input 3

8
1 3 9 7 3 3 7 9

Output 3

0
7
5
3
4
5
3
5

Input 4

10
1 1 1 1 1 1 1 1 1 1

Output 4

45
37
31
27
25
25
27
31
37
45