九条可怜是一个懒惰的女孩子：这道题她懒得想和九条可怜相关的背景了，你只要知道这题和九条可怜有关就行了。

从前有 $n$ 个村庄，它们之间有 $n-1$ 条道路，第 $i$ 条道路连接着村庄 $i$ 和 $i+1$。每年放假的时候，每个村庄的人都会出去玩，第 $i$ 个村庄的人想要去第 $p_i$ 个村庄。保证 $p$ 是一个长度为 $n$ 的排列。注意可能有一些村子里面的人都不想出去玩，所以可能会有 $p_i=i$ 的情况。

这些村庄之间的交通系统比较奇怪：如果当前在第 $i$ 个村庄的人想要出发前往第 $i+1$ 个村庄，那么原来在第 $i+1$ 个村庄的人也必须走到第 $i$ 个村庄。简单来说，每一次移动都是交换当前处在相邻村庄的人的位置。

在一些道路上会有哨卡。如果一次交换涉及的道路上存在哨卡，那要付出 $1$ 的过路费，否则不用交费。所有村庄的人都足够聪明且都以集体利益为重：他们总是会采用总代价最小的方法来实现他们的旅游计划。

第 $0$ 年的时候，所有道路上都没有哨卡。在接下来的 $n-1$ 年中，政府打算每年都在一条道路上建立哨卡（这样 $n-1$ 年后所有道路上就都有哨卡了）。建立哨卡的计划是一个长度为 $n-1$ 的排列 $q$，表示第 $i$ 年会在第 $q_i$ 条边上建立哨卡。

现在该出排列 $p,q$，你需要对 $i \in [1,n-1]$，输出第 $i$ 年为了完成旅游计划，村民们一共要付出多少钱。假设每一年建立哨卡的时间总是在旅游之前，且每一年你只需要考虑村民出发去游玩的的花费，在游玩结束后村民会瞬移回自己原来所在的村庄。

输入格式

第一行输入一个整数 $n(n \geq 2)$ 表示村庄的数量。

第二行输入一个长度为 $n$ 的排列，第三行输入一个长度为 $n-1$ 的排列，分别表示旅游计划和建造哨卡的计划。

本题分为 $4$ 个子任务，你需要通过所有子任务中的所有测试点，才能拿到这个子任务的分数：

输出格式

输出一行 $n-1$ 个整数，第 $i$ 个整数表示第 $i$ 年的最小花费。

样例数据

样例 1 输入

3
3 2 1
1 2

样例 1 输出

2 3

样例 2 输入

10
10 5 2 6 7 8 3 1 9 4
7 6 5 2 9 8 3 4 1

样例 2 输出

13 18 19 23 24 24 24 24 25

子任务

子任务一（$13$ 分），$n \leq 8$。

子任务二（$29$ 分），$n \leq 400$。

子任务三（$17$ 分），$n \leq 5000$。

子任务四（$41$ 分），$n \leq 3 \times 10^5$。