题目描述

小张同学在一次意外中穿越到了倚天屠龙记的武侠世界，未来能够尽快回到自己的世界，小张在尝试了多次跳崖之后终于找到了藏有乾坤大挪移心法的山洞，乾坤大挪移非常厉害可以帮助小张穿越回来继续接受九年义务教育，小张开心极了 不过在修炼过程中 遇到了一些问题，同学们一起帮小张看一下吧！

修炼心法需要将 $N$（$1 \leq N \leq 7500$）个穴位排成一行，穴位1在最前面，穴位N在最后面，并且用1到N来表示每个穴位，从前到后第i个穴位的名称是$a_i$（$1 \leq a_i \leq N$）。

修炼心法的第二要求是当且仅当第$i$个穴位为$b_i$（$1 \leq b_i \leq N$）时候才算是正确的位置

然而小张并非是专业的武林人士，所以他无法直接排列他的穴位。他只能执行下面的操作：

选择两个整数 $l$ 和 $r$，使得 $1 \leq l \le r \leq N$。反转队伍中第 $l$ 个穴位到第 $r$ 个穴位之间的穴位的顺序。

小张想要知道这种操作的效果到底如何，求出对于所有N(N+1)/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

输入输出样例 #2

输入 #2

3
1 2 3
1 2 3

输出 #2

12

输入输出样例 #3

输入 #3

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

输出 #3

60

说明/提示

样例解释

样例 #1

如果 小张 选择 $(l=1,r=1)$，$(l=2,r=2)$ 或 $(l=3,r=3)$，则没有穴位正确 以下操作会导致一个穴位正确。

• $(l=1,r=2)$：FJ 反转第一个和第二个穴位的顺序，因此新队伍中穴位顺序将为 $[3,1,2]$。第一个穴位位置正确。
• $(l=2,r=3)$：FJ 反转第二个和第三个穴位的顺序，因此新队伍中穴位顺序将为 $[1,2,3]$。第二个穴位位置正确。
• $(l=1,r=3)$：FJ 反转第一个第二个和第三个穴位的顺序，因此新队伍中穴位顺序将为 $[2,3,1]$。第三个穴位位置正确。
• 所有六种操作中穴位正确的数量之和为0+0+0+1+1+1=3

子任务

• 测试点 4：$N\le 100$。
• 测试点 5：$N\le 5000$。
• 测试点 6-9：$a_i$，$b_i$ 均在范围 $[1,N]$ 内均匀随机生成。
• 测试点 10-15：$a_i$，$b_i$ 均在范围 $[1,2]$ 内均匀随机生成。
• 测试点 16-23：没有额外限制。