CF722C.Destroying Array

You are given an array consisting of n non-negative integers _a_1, _a_2, ..., a__n.

You are going to destroy integers in the array one by one. Thus, you are given the permutation of integers from 1 to n defining the order elements of the array are destroyed.

After each element is destroyed you have to find out the segment of the array, such that it contains no destroyed elements and the sum of its elements is maximum possible. The sum of elements in the empty segment is considered to be 0.

给你一个由 $n$ 个非负整数 $a_1, a_2, \dots, a_n$ 组成的数组。

你将逐个删除该数组中的整数。因此，你还会得到一个 $1$ 到 $n$ 的排列，它定义了数组中元素被删除的顺序。

每次删除一个元素后，你需要找出数组中一个不包含任何已被删除元素的连续子段，使得该子段内所有元素之和尽可能大。空子段的元素和定义为 $0$。

The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the length of the array.

The second line contains n integers _a_1, _a_2, ..., a__n (0 ≤ a__i ≤ 109).

The third line contains a permutation of integers from 1 to n — the order used to destroy elements.

输入的第一行包含一个整数 $n$（$1 ≤ n ≤ 100\,000$）—— 数组的长度。

第二行包含 $n$ 个整数 $a_1,\,a_2,\,...,\,a_n$（$0 ≤ a_i ≤ 10^9$）。

第三行包含一个 $1$ 到 $n$ 的排列——用于销毁元素的顺序。

Print n lines. The i-th line should contain a single integer — the maximum possible sum of elements on the segment containing no destroyed elements, after first i operations are performed.

输出 n 行。第 i 行应包含一个整数——在执行前 i 次操作后，所有不包含被摧毁元素的区间的元素和的最大值。

Consider the first sample:

1. Third element is destroyed. Array is now 1 3  *  5. Segment with maximum sum 5 consists of one integer 5.
2. Fourth element is destroyed. Array is now 1 3  *   * . Segment with maximum sum 4 consists of two integers 1 3.
3. First element is destroyed. Array is now  *  3  *   * . Segment with maximum sum 3 consists of one integer 3.
4. Last element is destroyed. At this moment there are no valid nonempty segments left in this array, so the answer is equal to 0.

考虑第一个样例：

1. 第三个元素被销毁。数组变为 1 3  \*  5。最大和为 5 的子段仅包含一个整数 5。
2. 第四个元素被销毁。数组变为 1 3  \*   \* 。最大和为 4 的子段包含两个整数 1 3。
3. 第一个元素被销毁。数组变为  \*  3  \*   \* 。最大和为 3 的子段仅包含一个整数 3。
4. 最后一个元素被销毁。此时数组中已不存在任何有效的非空子段，因此答案为 0。