Page not loading? Try clicking here.
Placeholder

#8257
Subtask

Cow Checkups 1s 1024MB

Problems

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.


Input

The first line contains an integer N.

The second line contains a_1, a_2, \ldots, a_N.

The third line contains b_1, b_2, \ldots, b_N.


Output

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.


Subtask

# Score Condition
#130
#270

Example #1

3
1 3 2
3 2 1
3
3
0
0

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.


Example #2

3
1 2 3
1 2 3
0
3
0
3

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).


Example #3

7
1 3 2 2 1 3 2
3 2 2 1 2 3 1
0
6
14
6
2
0
0
0

he two possible operations that cause 4 cows to be checked are (l=4,r=5) and (l=5,r=7).



Source

USACO 2025 January Bronze

You must sign in to write code.