Destroying Array

题意翻译

# 题目描述 给你一个由n个非负整数组成的数列 $a_1$ ，$a_2$ ，...，$a_n$ 。 你将要一个一个摧毁这个数列中的数。并且，现在给你一个由 1 到 n 组成的序列来告诉你每个数被摧毁的时间顺序。 每当一个元素被摧毁时，你需要找到这个当前数列中的未被摧毁的数组成的和最大的连续子序列，另外，如果当前剩余的序列是空的的话，最大和就是0。 # 输入输出格式 ## 输入格式 第一行包含一个整数n (1 <= n <= 100000) , 代表数列的长度。 第二行包含n个整数 $a_1$ ，$a_2$ ，...，$a_n$ (0 <= $a_i$ <= 10^9)。 第三行包含一个由1到n的整数组成的序列，代表数被摧毁的顺序。 ## 输出格式 输出有n行，第i行包含一个整数 —— 在第i个操作已经执行完之后，数列中连续的最大和。 # 说明 第一个样例： 1.第三个数被删除了，现在的数列是 1 3 x 5 ，5由一个数5组成。 2.第四个数被删除了，现在的数列是 1 3 x x ，4由两个数1和3组成。 3.第一个数被删除了，现在的数列是 x 3 x x ，3由一个数3组成。 4.最后一个剩下的数被删除了，现在的数列中没有东西啦，所以答案是0呢！ 感谢@FangHaosb 提供的翻译

题目描述

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 $ .

输入输出格式

输入格式

The first line of the input contains a single integer $ n $ ( $ 1<=n<=100000 $ ) — the length of the array. The second line contains $ n $ integers $ a_{1},a_{2},...,a_{n} $ ( $ 0<=a_{i}<=10^{9} $ ). The third line contains a permutation of integers from $ 1 $ to $ n $ — the order used to destroy elements.

输出格式

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.

输入输出样例

输入样例 #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

说明

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 $ .