给定一个由 n 个非负整数 a1, a2, ..., an 组成的数组。
你将一一销毁数组中的整数。因此,您将获得从 1 到 n 的整数排列,定义数组元素被破坏的顺序。
每个元素被破坏后,你必须找出数组的段,使其不包含被破坏的元素,并且其元素的总和尽可能最大。空段中的元素之和被认为是0。
输入
输入的第一行包含一个整数 n (1 ≤ n ≤ 100 000) — 数组的长度。
第二行包含 n 个整数 a1, a2, ..., an (0 ≤ ai ≤ 109)。
第三行包含从 1 到 n 的整数排列——用于销毁元素的顺序。
输出
打印 n 行。第 i 行应包含一个整数 - 在执行第 i 个操作后,不包含已损坏元素的段上元素的最大可能总和。
示例
输入 #1
4 1 3 2 5 3 4 1 2
输出 #1
5 4 3 0
输入 #2
5 1 2 3 4 5 4 2 3 5 1
输出 #2
6 5 5 1 0
输入 #3
8 5 5 4 4 6 6 5 5 5 2 8 7 1 3 4 6
输出 #3
18 16 11 8 8 6 6 0
注意
考虑第一个样本:
1. 第三个元素被破坏。数组现在为 1 3 * 5。最大总和为 5 的段由一个整数 5 组成。
2. 第四个元素被破坏。数组现在为 1 3 * * 。最大总和为 4 的段由两个整数 1 3 组成。
3. 第一个元素被破坏。数组现在为 * 3 * * 。总和最大为 3 的段由一个整数 3 组成。
4. 最后一个元素被破坏。此时该数组中已没有有效的非空段,因此答案等于 0。