题目描述

Farmer John 正在带他的有 $N$ 头奶牛去当地的奶牛医院进行体检，他让奶牛排成一行，奶牛 $1$ 在队伍的最前面，奶牛 $N$ 在队伍的最后面。

Farmer John 的奶牛有许多不同的品种，他习惯用从 $1$ 到 $N$ 的整数来表示每一品种。队伍从前到后第 $i$ 头奶牛的品种是 $a_i$ 。

然而兽医非常挑剔，他只愿意当队伍中第 $i$ 头奶牛为品种 $b_i$ 时才对它进行体检。

Farmer John 不想完全重新排列他的奶牛，于是他打算只执行以下操作一次：选择两个整数 $l$ 和 $r$，反转队伍中第 $l$ 头奶牛到第 $r$ 头奶牛之间的奶牛的顺序。

Farmer John 想要知道这种方法有多少效果，他想请求你帮忙，对于每一个 $c=0 \ldots N$，求出恰好能让 $c$ 头奶牛被检查的操作区间 $(l,r)$ 的数量。

注意：两种操作 $(l_1,r_1)$ 和 $(l_2,r_2)$ 不同，当且仅当 $l_1 \neq l_2$ 或者 $r_1 \neq r_2$。

输入格式

输入的第一行包含 $N$。

第二行包含 $a_1, a_2, \ldots, a_N$。

第三行包含 $b_1, b_2, \ldots, b_N$。

输出格式

输出 $N+1$ 行，第 $i$ 行包含使得 $i-1$ 头奶牛被检查的不同操作区间 $(l,r)$ 的数量。

输入输出样例 #1

输入 #1

3
1 3 2
3 2 1

输出 #1

3
3
0
0

当 $c=0$ ，如果 Farmer John 选择 $(l=1,r=1)$，$(l=2,r=2)$ 或 $(l=3,r=3)$，则没有奶牛将会被检查。

当 $c=1$ ，以下操作可以让一头奶牛被检查：

• $(l=1,r=2)$：FJ 反转第一头和第二头奶牛的顺序，因此新队伍中每头奶牛的品种将为 $[3,1,2]$。第一头奶牛将会被检查。
• $(l=2,r=3)$：FJ 反转第二头和第三头奶牛的顺序，因此新队伍中每头奶牛的品种将为 $[1,2,3]$。第二头奶牛将会被检查。
• $(l=1,r=3)$：FJ 反转第一头，第二头和第三头奶牛的顺序，因此新队伍中每头奶牛的品种将为 $[2,3,1]$。第三头奶牛将会被检查。

输入输出样例 #2

输入 #2

3
1 2 3
1 2 3

输出 #2

0
3
0
3

三种导致 $3$ 头奶牛被检查的可能操作为 $(l=1,r=1)$，$(l=2,r=2)$ 和 $(l=3,r=3)$。

输入输出样例 #3

输入 #3

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

输出 #3

0
6
14
6
2
0
0
0

两种导致 $4$ 头奶牛被检查的可能操作为 $(l=4,r=5)$ 和 $(l=5,r=7)$。

数据范围

对于 $100\%$ 的数据，有 $1 \leq N \leq 7500 , 1 \leq a_i \leq N , 1 \leq b_i \leq N , 1 \leq l \le r \leq N$ 。

子任务

• 测试点 4-6: $N\le 100$
• 测试点 7-13: 无特殊限制

时限：2s

空间：256MB