Cow Checkups | Code Joint

**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 \leq 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 \dots 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}$ .

If FJ chooses ( $l = 1, r = 1$ ), ( $l = 2, r = 2$ ), or ( $l = 3, r = 3$ ) then no cows will be checked. Note that those operations do not modify any of the cows' locations.

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.

The three possible operations that cause $3$ cows to be checked are ( $l = 1, r = 1$ ), ( $l = 2, r = 2$ ), and ( $l = 3, r = 3$ ). The two possible operations that cause $4$ cows to be checked are ( $l = 4, r = 5$ ) and ( $l = 5, r = 7$ ).

SCORING:

Inputs 4-6: $N \leq 100$
Inputs 7-13: No additional constraints

Problem credits: Chongtian Ma and Haokai Ma

Source: USA Computing Olympiad.

Input Format

The first line contains an integer $N$ .

The second line contains $a_{1}, a_{2}, \dots, a_{N}$ .

The third line contains $b_{1}, b_{2}, \dots, b_{N}$ .

Output Format

Output $N + 1$ lines with the $i$ -th line containing the number of distinct operations ( $l, r$ ) that result in $i - 1$ cows being checked.

Sample Input 1

3 1 3 2 3 2 1

Sample Output 1

3 3 0 0

Sample Input 2

3 1 2 3 1 2 3

Sample Output 2

0 3 0 3

Sample Input 3

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

Sample Output 3

0 6 14 6 2 0 0 0

Submit

Language