**Note: We suggest using a language other than Python to earn full credit on this problem.**

Farmer John's $N$ ($1 \leq N \leq 7500$) cows are standing in a line, with cow $1$ at the front of the line and cow $N$ at the back of the line. FJ's cows also come in many different species. He denotes each species with an integer from $1$ to $N$. The $i$'th cow from the front of the line is of species $a_i$ ($1 \leq a_i \leq N$).

FJ is taking his cows to a checkup at a local bovine hospital. However, the bovine veterinarian is very picky and wants to perform a checkup on the $i$'th cow in the line, only if it is of species $b_i$ ($1 \leq b_i \leq N$).

FJ is lazy and does not want to completely reorder his cows. He will perform the following operation exactly once.

• Select two integers $l$ and $r$ such that $1 \leq l \le r \leq N$. Reverse the order of the cows that are between the $l$-th cow and the $r$-th cow in the line, inclusive.

FJ wants to measure how effective this approach is. For each $c=0 \ldots N$, help FJ find the number of distinct operations ($l,r$) that result in exactly $c$ cows being checked. Two operations ($l_1,r_1$) and ($l_2,r_2$) are different if $l_1 \neq l_2$ or $r_1 \neq r_2$.

SAMPLE INPUT:

3
1 3 2
3 2 1

SAMPLE OUTPUT:

3
3
0
0

The following operations result in one cow being checked.

• $l=1,r=2$: FJ reverses the order of the first and second cows so the species of each cow in the new lineup will be $[3,1,2]$. The first cow will be checked.
• $l=2,r=3$: FJ reverses the order of the second and third cows so the species of each cow in the new lineup will be $[1,2,3]$. The second cow will be checked.
• $l=1,r=3$: FJ reverses the order of the first, second, and third cows so the species of each cow in the new lineup will be $[2,3,1]$. The third cow will be checked.

SAMPLE INPUT:

3
1 2 3
1 2 3

SAMPLE OUTPUT:

0
3
0
3

SAMPLE INPUT:

7
1 3 2 2 1 3 2
3 2 2 1 2 3 1

SAMPLE OUTPUT:

0
6
14
6
2
0
0
0

Problem credits: Chongtian Ma and Haokai Ma