**Note: We suggest using a language other than Python to earn full credit on this problem.**
Farmer John's N (1≤N≤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 ai (1≤ ai ≤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 bi (1≤bi≤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≤l≤r≤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…N, help FJ find the number of distinct operations (l,r) that result in exactly c cows being checked. Two operations (l1,r1) and (l2,r2) are different if l1≠l2 or r1≠r2.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains an integer N.
The second line contains a1,a2,...,aN.
The third line contains b1,b2,…,bN.
OUTPUT FORMAT (print output to the terminal / stdout):
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:
3
1 3 2
3 2 1
SAMPLE OUTPUT:
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.
SAMPLE INPUT:
3
1 2 3
1 2 3
SAMPLE OUTPUT:
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).
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
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≤100
Inputs 7-13: No additional constraints
Problem credits: Chongtian Ma and Haokai Ma
扫码领取USACO试题答案+详细解析
咨询一对一备赛规划
