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.


-----Input-----

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} ≤ 10^9). 

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


-----Output-----

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.


-----Examples-----
Input
4
1 3 2 5
3 4 1 2

Output
5
4
3
0

Input
5
1 2 3 4 5
4 2 3 5 1

Output
6
5
5
1
0

Input
8
5 5 4 4 6 6 5 5
5 2 8 7 1 3 4 6

Output
18
16
11
8
8
6
6
0



-----Note-----

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

Difficulty: competition

Starter code:

Solutions:
__author__ = 'Think'
n=int(input())
aints=[int(i) for i in input().split()]
permutes=[int(i)-1 for i in input().split()]
results=[0]

rebuilt={}
m=0
for numby in range(n-1, 0, -1):
	p=permutes[numby]
	below=False
	above=False
	if p-1 in rebuilt:
		below=True
	if p+1 in rebuilt:
		above=True
	if above and below:
		bsum, bottom=rebuilt[p-1]
		asum, top=rebuilt[p+1]
		new=bsum+asum+aints[p]
		rebuilt[bottom]=(new, top)
		rebuilt[top]=(new, bottom)
	elif above or below:
		if above:
			other=p+1
		else:
			other=p-1
		psum, prev=rebuilt[other]
		new=psum+aints[p]
		rebuilt[prev]=(new, p)
		rebuilt[p]=(new, prev)
	else:
		new=aints[p]
		rebuilt[p]=(new, p)
	m=max(new, m)
	results.append(m)
for numby in range(n-1, -1, -1):
	print(results[numby])




input()
array = [int(n) for n in input().split()]
order = [int(n)-1 for n in input().split()][::-1]
rights = dict()
lefts = dict()
current_max = 0
results = []
for i in order:
    results.append(current_max)
    if i-1 in rights and i+1 in lefts:
        segment_sum = rights[i-1][1]+lefts[i+1][1]+array[i]
        rights[lefts[i+1][0]] = [rights[i-1][0], segment_sum]
        lefts[rights[i-1][0]] = [lefts[i+1][0], segment_sum]
        rights.pop(i-1)
        lefts.pop(i+1)
    elif i-1 in rights:
        segment_sum = rights[i-1][1]+array[i]
        lefts[rights[i-1][0]] = [i, segment_sum]
        rights[i] = [rights[i-1][0], segment_sum] 
        rights.pop(i-1)
    elif i+1 in lefts:
        segment_sum = lefts[i+1][1]+array[i]
        rights[lefts[i+1][0]] = [i, segment_sum]
        lefts[i] = [lefts[i+1][0], segment_sum] 
        lefts.pop(i+1)        
    else:
        segment_sum = array[i]
        lefts[i] = [i, segment_sum]
        rights[i] = [i, segment_sum]
    if segment_sum > current_max:
        current_max = segment_sum
print(*results[::-1], sep="\n")


def main():
    def f(x):
        l = []
        while x != clusters[x]:
            l.append(x)
            x = clusters[x]
        for y in l:
            clusters[y] = x
        return x

    n, aa = int(input()), [0, *list(map(int, input().split())), 0]
    l, clusters, mx = list(map(int, input().split())), [0] * (n + 2), 0
    for i in range(n - 1, -1, -1):
        a = clusters[a] = l[i]
        l[i] = mx
        for i in a - 1, a + 1:
            if clusters[i]:
                j = f(i)
                aa[a] += aa[j]
                clusters[j] = a
                f(i)
        if mx < aa[a]:
            mx = aa[a]
    print('\n'.join(map(str, l)))


def __starting_point():
    main()

__starting_point()

def main():
    n, aa = int(input()), [0, *list(map(int, input().split())), 0]
    l, clusters, mx = list(map(int, input().split())), [0] * (n + 2), 0
    for i in range(n - 1, -1, -1):
        a = clusters[a] = l[i]
        l[i] = mx
        for i in a - 1, a + 1:
            if clusters[i]:
                stack, j = [], i
                while j != clusters[j]:
                    stack.append(j)
                    j = clusters[j]
                for i in stack:
                    clusters[i] = j
                aa[a] += aa[j]
                clusters[j] = a
        if mx < aa[a]:
            mx = aa[a]
    print('\n'.join(map(str, l)))


def __starting_point():
    main()

__starting_point()

def make_set(a):
    size[a] = 1
    parent[a] = a
    anses[a] = A[a]
    
def find_set(a):
    if a == parent[a]:
        return a
    else:
        parent[a] = find_set(parent[a])
    return parent[a]

def union_sets(a,b):
    a = find_set(a)
    b = find_set(b)
    if a != b:
        if size[b] > size[a]:
            a,b=b,a
        parent[b] = a
        size[a] += size[b]
        anses[a] +=anses[b]
    return anses[a]
    
    
size = dict()
parent=dict()
anses=dict()
n = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
ans = 0
answer = [0]
for j in range(len(B)-1,0,-1):
    j = B[j]-1
    make_set(j)
    per = anses[j]
    if (j+1) in parent:
        per = union_sets(j,j+1)
    if (j-1) in parent:
        per = union_sets(j,j-1)
    ans = max(ans,per)
    answer.append(ans)
for j in range(n-1,-1,-1):
    print(answer[j])

3
size = int(input())
num = list(map(int, input().split()))
rem = reversed(list(map(lambda x: int(x) - 1, input().split())))
chunks = [None] * size
res = [-1] * size
ans = [0] * size
ms = -1

def addChunk(n):
    chunks[n] = [n, num[n]]
    return n

def getRoot(n):
    while chunks[n][0] != n:
        n = chunks[n][0]
    return n

def mergeChunks(parent, child):
    proot = getRoot(parent)
    croot = getRoot(child)
    chunks[croot][0] = proot
    chunks[proot][1] += chunks[croot][1]
    return proot

for i in rem:
    res[i] = num[i]
    root = addChunk(i)
    if i > 0 and chunks[i - 1] != None:
        root = mergeChunks(i - 1, i)
    if i + 1 < size and chunks[i + 1] != None:
        root = mergeChunks(i, i + 1)
    ms = max(ms, chunks[root][1])
    ans.append(ms)
    
for i in range(1, size):
    print (ans[-i-1])
    
print(0)

def make_set(a):
    size[a] = 1
    parent[a] = a
    anses[a] = A[a]
    
def find_set(a):
    if a == parent[a]:
        return a
    else:
        parent[a] = find_set(parent[a])
    return parent[a]

def union_sets(a,b):
    a = find_set(a)
    b = find_set(b)
    if a != b:
        if size[b] > size[a]:
            a,b=b,a
        parent[b] = a
        size[a] += size[b]
        anses[a] +=anses[b]
    return anses[a]
    
    
size = dict()
parent=dict()
anses=dict()
n = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
ans = 0
answer = [0]
for j in range(len(B)-1,0,-1):
    j = B[j]-1
    make_set(j)
    per = anses[j]
    if (j+1) in parent:
        per = union_sets(j,j+1)
    if (j-1) in parent:
        per = union_sets(j,j-1)
    ans = max(ans,per)
    answer.append(ans)
for j in range(n-1,-1,-1):
    print(answer[j])

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Fri Dec  9 16:14:34 2016

@author: kostiantyn.omelianchuk
"""

from sys import stdin, stdout
lines = stdin.readlines()
n = int(lines[0])
a = [int(x)  for x in lines[1].split()]
b = [int(x)  for x in lines[2].split()]

check_array = [0 for i in range(n)]
snm = [i for i in range(n)]
r = [1 for i in range(n)]
sums = dict(list(zip(list(range(n)), a)))    

def find_x(x):
    if snm[x] != x:
        snm[x] = find_x(snm[x])
    return snm[x]


def union(x_start, y_start):
    x = find_x(x_start)
    y = find_x(y_start)
    sums[x] += sums[y]
    sums[y] = sums[x]
    if x == y:
        return x
        #sums[x] += sums[x_start]
    if r[x] == r[y]:
        r[x] += 1
    if r[x] < r[y]:
        snm[x] = y
        return y
    else:
        snm[y] = x
        return x
    

max_list = []
total_max = 0

for i in range(n):
    cur_sum = 0
    flag = 0
    
    max_list.append(total_max)
    #pos = n-i-1

    elem = b[n-i-1] - 1
    check_array[elem] = 1
    #pos_x = find_x(elem)
    if elem>0:
        if check_array[elem-1] == 1:
            pos = union(elem-1,elem)
            cur_sum = sums[pos]
            #print(sums, check_array, total_max, cur_sum, elem, find_x(elem))
            
        else:
            flag += 1
    else:
        flag += 1
    if elem<(n-1):
        if check_array[elem+1] == 1:
            pos = union(elem,elem+1)
            cur_sum = sums[pos]
            #print(sums, check_array, total_max, cur_sum, elem, find_x(elem))
            
        else:
            flag += 1
    else:
        flag += 1
    if flag == 2:
        total_max = max(total_max,sums[elem])
    else:
        total_max = max(cur_sum, total_max)
    
        
max_list.append(total_max)

for j in range(1,n+1):
    print(max_list[n-j])
    
    
    
    
    


n=int(input())
l=list(map(int,input().split()))
l1=list(map(int,input().split()))
l1=l1[::-1]
mi=0
V=[0]
L=[[] for i in range(n)]
for i in range(n-1) :
    a=l1[i]-1
    b=l1[i]-1
    s=l[l1[i]-1]
    if a-1!=-1 :
        if L[a-1] :
            s+=L[a-1][0]
            a=L[a-1][1]
    if b+1<n :
        if L[b+1] :
            s+=L[b+1][0]
            b=L[b+1][2]
    L[a]=[s,a,b]
    L[b]=[s,a,b]
    mi=max(mi,s)
    V.append(mi)
for i in range(n-1,-1,-1) :
    print(V[i])
    
    
    


def main():
    n, aa = int(input()), [0, *list(map(int, input().split())), 0]
    l, clusters, mx = list(map(int, input().split())), [0] * (n + 2), 0
    for i in range(n - 1, -1, -1):
        a = clusters[a] = l[i]
        l[i] = mx
        for i in a - 1, a + 1:
            if clusters[i]:
                stack, j = [], i
                while j != clusters[j]:
                    stack.append(j)
                    j = clusters[j]
                for i in stack:
                    clusters[i] = j
                aa[a] += aa[j]
                clusters[j] = a
        if mx < aa[a]:
            mx = aa[a]
    print('\n'.join(map(str, l)))


def __starting_point():
    main()




# Made By Mostafa_Khaled

__starting_point()

n=int(input())
a=list(map(int,input().split()))
d=list(map(int,input().split()))
q=[[i,i,-1] for i in range(n)]
o=['0']
m=-1
for i in reversed(d[1:]):
    i-=1
    q[i][2]=a[i]
    l,r=i,i
    if i<n-1 and q[i+1][2]!=-1:
        r=q[i+1][1]
        q[r][2]+=a[i]
    if i>0 and q[i-1][2]!=-1:
        l=q[i-1][0]
        q[l][2]+=a[i]
    q[l][1]=r
    q[r][0]=l
    q[l][2]+=q[r][2]-a[i]
    q[r][2]=q[l][2]
    m=max(m,q[r][2])
    o.append(str(m))
print('\n'.join(reversed(o)))

# TODO: type solution here
class Node(object):
    def __init__(self, label):
        self.label = label
        self.par = self
        self.size = 1
        self.sum = 0
        self.seen = False


class DisjointSet(object):
    def __init__(self, n):
        self.n = n
        self.nodes = [Node(i) for i in range(n)]

    def find(self, u):
        if u != u.par:  # here we user path compression trick
            u.par = self.find(u.par)
        return u.par

    def unite(self, u, v):
        u, v = self.find(u), self.find(v)
        if u == v:  # u and v are in the same component
            return False

        # making v the vertex with bigger size
        if u.size > v.size:
            u, v = v, u

        # merging two components
        u.par = v

        # updating maximum size as size
        v.size += u.size
        v.sum += u.sum

        return True


n = int(input())
nums = [int(a) for a in input().split(" ")]
perm = [int(a) - 1 for a in input().split(" ")]
answers = []
current_answer = 0
dsu = DisjointSet(n)


def add(i, current_answer):
    node = dsu.nodes[i]
    node.seen = True
    node.sum = nums[i]
    if i > 0 and dsu.nodes[i - 1].seen:
        dsu.unite(node, dsu.nodes[i - 1])
    if i < n - 1 and dsu.nodes[i + 1].seen:
        dsu.unite(node, dsu.nodes[i + 1])

    parent = dsu.find(node)
    current_answer = max(current_answer, parent.sum)
    return current_answer


for i in range(n - 1, -1, -1):
    answers.append(current_answer)
    current_answer = add(perm[i], current_answer)

for i in range(n):
    print(answers[n - i - 1])


n = int(input())
a = list(map(int, input().split()))
p = list(map(int, input().split()))

valid = [False for i in range(n)]
parent = [0] * n
size = [0] * n
stat = [0] * n

def find(x):
    while parent[x] != x:
        x = parent[x]
    return x

def union(a, b):
    x = find(a)
    y = find(b)
    if x == y:
        return
    elif size[x] < size[y]:
        parent[x] = y
        size[y] += size[x]
        stat[y] += stat[x]
    else:
        parent[y] = x
        size[x] += size[y]
        stat[x] += stat[y]

ans = [0]

for i in range(n - 1, 0, -1):
    k = p[i] - 1
    valid[k] = True
    parent[k] = k
    stat[k] = a[k]
    if k > 0 and valid[k - 1]:
        union(k, k - 1)
    if k < n - 1 and valid[k + 1]:
        union(k, k + 1)
    
    t = stat[find(k)]
    m = max(ans[-1], t)
    ans.append(m)

while len(ans) > 0:
    print(ans.pop())

class DSU:
    def __init__(self, n):
        self.par = list(range(n))
        self.arr = list(map(int, input().split()))
        self.siz = [1] * n
        self.sht = [0] * n
        self.max = 0
    def find(self, n):
        nn = n
        while nn != self.par[nn]:
            nn = self.par[nn]
        while n != nn:
            self.par[n], n = nn, self.par[n]
        return n
    def union(self, a, b):
        a = self.find(a)
        b = self.find(b)
        
        if a == b:
            return
        
        if self.siz[a] < self.siz[b]:
            a, b = b, a
        self.par[b] = a
        self.siz[a] += self.siz[b]
        self.arr[a] += self.arr[b]
        if self.arr[a] > self.max:
            self.max = self.arr[a]
    def add_node(self, n):
        self.sht[n] = 1
        if self.arr[n] > self.max:
            self.max = self.arr[n]
        if n != len(self.par) - 1 and self.sht[n + 1]:
            self.union(n, n + 1)
        if n != 0 and self.sht[n - 1]:
            self.union(n, n - 1)
        

def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    dsu = DSU(n)
    per = list(map(int, input().split()))
    ans = [0] * n
    for i in range(n):
        ans[~i] = dsu.max
        dsu.add_node(per[~i] - 1)
    for x in ans:
        print(x)
    return 0

main()

import sys
input = sys.stdin.readline

class Unionfind:
    def __init__(self, n):
        self.par = [-1]*n
        self.rank = [1]*n
    
    def root(self, x):
        p = x
        
        while not self.par[p]<0:
            p = self.par[p]
        
        while x!=p:
            tmp = x
            x = self.par[x]
            self.par[tmp] = p
        
        return p
    
    def unite(self, x, y):
        rx, ry = self.root(x), self.root(y)
        
        if rx==ry: return False
        
        if self.rank[rx]<self.rank[ry]:
            rx, ry = ry, rx
        
        self.par[rx] += self.par[ry]
        self.par[ry] = rx
    
        if self.rank[rx]==self.rank[ry]:
            self.rank[rx] += 1
    
    def is_same(self, x, y):
        return self.root(x)==self.root(y)
    
    def count(self, x):
        return -self.par[self.root(x)]

n = int(input())
a = list(map(int, input().split()))
p = list(map(int, input().split()))
uf = Unionfind(n)
V = [0]*n
flag = [False]*n
ans = [0]

for pi in p[::-1]:
    pi -= 1
    V[pi] = a[pi]
    flag[pi] = True
    
    if pi-1>=0 and flag[pi-1]:
        v = V[uf.root(pi-1)]+V[uf.root(pi)]
        uf.unite(pi-1, pi)
        V[uf.root(pi)] = v
    
    if pi+1<n and flag[pi+1]:
        v = V[uf.root(pi+1)]+V[uf.root(pi)]
        uf.unite(pi, pi+1)
        V[uf.root(pi)] = v
    
    ans.append(max(ans[-1], V[uf.root(pi)]))

for ans_i in ans[:-1][::-1]:
    print(ans_i)

# Bosdiwale code chap kr kya milega
# Motherfuckers Don't copy code for the sake of doing it
# ..............
# ╭━┳━╭━╭━╮╮
# ┃┈┈┈┣▅╋▅┫┃
# ┃┈┃┈╰━╰━━━━━━╮
# ╰┳╯┈┈┈┈┈┈┈┈┈◢▉◣
# ╲┃┈┈┈┈┈┈┈┈┈┈▉▉▉
# ╲┃┈┈┈┈┈┈┈┈┈┈◥▉◤
# ╲┃┈┈┈┈╭━┳━━━━╯
# ╲┣━━━━━━┫
# ……….
# .……. /´¯/)………….(\¯`\
# …………/….//……….. …\\….\
# ………/….//……………....\\….\
# …./´¯/…./´¯\……/¯ `\…..\¯`\
# ././…/…/…./|_…|.\….\….\…\.\
# (.(….(….(…./.)..)...(.\.).).)
# .\…………….\/../…....\….\/…………/
# ..\…………….. /……...\………………../
# …..\…………… (………....)……………./

n = int(input())
arr = list(map(int,input().split()))
ind = list(map(int,input().split()))
parent = {}
rank = {}
ans = {}
total = 0
temp = []
def make_set(v):
    rank[v] = 1
    parent[v] = v
    ans[v] = arr[v]

def find_set(u):
    if u==parent[u]:
        return u
    else:
        parent[u] = find_set(parent[u])
    return parent[u]

def union_set(u,v):
    a = find_set(u)
    b = find_set(v)
    if a!=b:
        if rank[b]>rank[a]:
            a,b = b,a
        parent[b] = a
        rank[a]+=rank[b]
        ans[a]+=ans[b]
    return ans[a]

for i in range(n-1,-1,-1):
    rem = ind[i]-1
    make_set(rem)
    final = ans[rem]
    if rem+1 in parent:
        final = union_set(rem,rem+1)
    if rem-1 in parent:
        final = union_set(rem,rem-1)
    total = max(total,final)
    temp.append(total)
temp[-1] = 0
temp = temp[-1::-1]
temp = temp[1::]
for i in temp:
    print(i)
print(0)

n=int(input())
arr=[int(i) for i in input().split()]
des=[int(i) for i in input().split()]
ans=0
left=[-1 for i in range(n)]
right=[-1 for i in range(n)]
last=0
presum=[]
parr=[]
for i in arr:
    presum.append(last+i)
    last+=i
for i in des[::-1]:
    l=0;r=0
    parr.append(ans)
    if i==1 or left[i-2]==-1:
        left[i-1]=i-1
    else:
        left[i-1]=left[i-2]
    l=left[i-1]
    if i==n or right[i]==-1:
        right[i-1]=i-1
    else:
        right[i-1]=right[i]
    r=right[i-1]
    if l==0 and ans<presum[r]:
        ans=presum[r]
    elif ans<presum[r]-presum[l-1]:
        ans=presum[r]-presum[l-1]
    left[r]=l
    right[l]=r
for i in parr[::-1]:
    print(i)



import sys

MAX = 100005
arr = MAX * [0]
pre = MAX * [0]
ix = MAX * [0]
sun = MAX * [0]
ans = MAX * [0]
vis = MAX * [False]
mx = 0


def find(x):
    if x == pre[x]:
        return x
    pre[x] = find(pre[x])
    return pre[x]


def unite(x, y):

    dx = find(x)
    dy = find(y)
    if dx == dy:
        return
    pre[dx] = dy
    sun[dy] += sun[dx]


n = int(input())
arr = [int(i) for i in input().split()]
arr.insert(0, 0)
sun = arr
pre = [i for i in range(n+1)]
ix = [int(i) for i in input().split()]


for i in range(n-1, -1, -1):
    x = ix[i]
    ans[i] = mx
    vis[x] = True
    if x != 1 and vis[x-1]:
        unite(x-1, x)
    if x != n and vis[x+1]:
        unite(x, x+1)
    mx = max(mx, sun[find(x)])

for i in range(n):
    print(ans[i])