← 返回题目列表

Codeforces · 722/C

C. 销毁阵列

中文机器翻译题面 查看原题

给定一个由 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。