CF722C Destroying Array

Statement

An array of n non-negative integers is destroyed one position at a time in a given order. After every operation, find the maximum sum of a contiguous segment containing no destroyed position. The empty segment has sum 0.

Input

The first line contains n (1 <= n <= 100000). The second line contains a_i (0 <= a_i <= 10^9). The third line is a permutation of 1..n, the destruction order.

Output

Print n lines. Line i is the maximum remaining segment sum after the first i destructions.

Example

4
1 3 2 5
3 4 1 2

5
4
3
0