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.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Spanning trees

Data structures


Solutions:
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)


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 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])


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, *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)))
main()


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])


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda : list(map(int, sys.stdin.readline().rstrip('\r\n').split()))
mod = 10 ** 9 + 7
Mod = 998244353
INF = float('inf')
sys.setrecursionlimit(2 * 10 ** 5 + 100)
from heapq import *
n = int(input())
a = [0] + list(map(int, input().split()))
b = list(map(int, input().split()))
ans = []
best = 0
vis = [False for i in range(n + 1)]
value = a.copy()
par = [-1] * (n + 1)

def find(c):
	if par[c] < 0:
		return (c, -value[c])
	(par[c], trash) = find(par[c])
	return (par[c], trash)

def union(a1, b1):
	if vis[b1] == False:
		return value[a1]
	(pa, val1) = find(a1)
	(pb, val2) = find(b1)
	if pa == pb:
		return False
	if par[pa] > par[pb]:
		par[pb] += par[pa]
		par[pa] = pb
		value[pb] += value[pa]
		return value[pb]
	else:
		par[pa] += par[pb]
		par[pb] = pa
		value[pa] += value[pb]
		return value[pa]
for i in range(n):
	ans.append(best)
	ind = b.pop()
	vis[ind] = True
	if ind + 1 <= n:
		res = union(ind, ind + 1)
		if res:
			best = max(best, res)
	if ind - 1 > 0:
		res = union(ind, ind - 1)
		if res:
			best = max(best, res)
for i in ans[::-1]:
	print(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()
__starting_point()


import sys
import threading

def main():

	def find(a):
		if dsu[a] == a:
			return a
		wtf = []
		while dsu[a] != a:
			wtf.append(a)
			a = dsu[a]
		for i in wtf:
			dsu[i] = a
		return a

	def union(a, b):
		a = find(a)
		b = find(b)
		if (a + b) % 2:
			dsu[a] = b
			slov[b] = slov[a] + slov[b]
		else:
			dsu[b] = a
			slov[a] = slov[a] + slov[b]
	n = int(input())
	sys.setrecursionlimit(min(10 * n, 1000000))
	dsu = [i for i in range(n + 1)]
	koord = [0] * n
	used = [False] * n
	c = list(map(int, input().split()))
	f = list(reversed(list(map(lambda x: int(x) - 1, input().split()))))
	if n == 1:
		print(0)
		exit(0)
	dsu = [i for i in range(n)]
	summ = [0] * n
	ans = [0]
	slov = c[:]
	for d in f:
		used[d] = True
		m = 0
		if d == 0:
			if used[d + 1]:
				head = union(d + 1, d)
		elif d == n - 1:
			if used[d - 1]:
				union(d - 1, d)
		else:
			if used[d - 1]:
				union(d - 1, d)
			if used[d + 1]:
				union(d + 1, d)
		m = slov[find(d)]
		m = max(slov[d], m)
		ans.append(max(m, ans[-1]))
	for i in range(n):
		print(ans[-i - 2])
main()


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
	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)
	elem = b[n - i - 1] - 1
	check_array[elem] = 1
	if elem > 0:
		if check_array[elem - 1] == 1:
			pos = union(elem - 1, elem)
			cur_sum = sums[pos]
		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]
		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])


from sys import stdin
input = 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()))
flag = [False] * n
ans = [0]
val = [0] * n
uf = Unionfind(n)
for i in range(n)[::-1]:
	pp = p[i] - 1
	flag[pp] = True
	val[pp] = a[pp]
	if pp > 0 and flag[pp - 1]:
		tmp = val[uf.root(pp)] + val[uf.root(pp - 1)]
		uf.unite(pp - 1, pp)
		val[uf.root(pp)] = tmp
	if pp < n - 1 and flag[pp + 1]:
		tmp = val[uf.root(pp)] + val[uf.root(pp + 1)]
		uf.unite(pp + 1, pp)
		val[uf.root(pp)] = tmp
	ans.append(max(ans[-1], val[uf.root(pp)]))
print(*ans[:-1][::-1], sep='\n')


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])


import sys
input = sys.stdin.buffer.readline

def solution():
	n = int(input())
	l = list(map(int, input().split()))
	p = list(map(int, input().split()))
	pre = [0] * 200000
	low = [0] * 200000
	high = [0] * 200000
	ans = 0
	a = []
	for i in range(n):
		pre[i + 1] = pre[i] + l[i]
	for i in range(n - 1, -1, -1):
		a.append(ans)
		lo = low[p[i] - 1]
		h = high[p[i] + 1]
		if lo == 0:
			lo = p[i]
		if h == 0:
			h = p[i]
		high[lo] = h
		low[h] = lo
		ans = max(ans, pre[h] - pre[lo - 1])
	a.reverse()
	for i in a:
		print(i)
solution()


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 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:
			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:
			return False
		if u.size > v.size:
			(u, v) = (v, u)
		u.par = v
		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())
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)


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)))


import sys, os, io
from sys import stdin
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
curMax = 0
summ = defaultdict(lambda : 0)

def find(e, parent):
	if parent[e] == e:
		return e
	parent[e] = find(parent[e], parent)
	return parent[e]

def union(a, b, parent, arr):
	global curMax
	if find(a, parent) == find(b, parent):
		return
	if parent[a] == a and filled[a] == -1:
		summ[parent[a]] += arr[a]
		filled[a] = 1
	if parent[b] == b and filled[b] == -1:
		summ[parent[b]] += arr[b]
		filled[b] = 1
	filled[a] = 1
	filled[b] = 1
	summ[parent[a]] = summ[parent[a]] + summ[parent[b]]
	summ[parent[b]] = 0
	curMax = max(curMax, summ[parent[a]])
	parent[b] = parent[a]
for _ in range(1):
	n = ii()
	a = li()
	orderofDestroy = [int(x) - 1 for x in input().split()]
	temp = [[-1, -1] for i in range(n)]
	a1 = []
	m = 0
	for i in range(n - 1, 0, -1):
		l = r = orderofDestroy[i]
		curSum = a[l]
		if l > 0:
			if temp[l - 1][0] != -1:
				curSum += temp[l - 1][0][0]
				l = temp[l - 1][0][1]
		if r < n - 1:
			if temp[r + 1][1] != -1:
				curSum += temp[r + 1][1][0]
				r = temp[r + 1][1][1]
		temp[l][1] = [curSum, r]
		temp[r][0] = [curSum, l]
		m = max(m, curSum)
		a1.append(m)
a1.reverse()
a1.append(0)
for i in range(n):
	print(a1[i])


__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])


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)


import os
from io import BytesIO

class IO:

	def __init__(self):
		self.input = BytesIO(os.read(0, os.fstat(0).st_size)).readline

	def read_int(self):
		return int(self.input())

	def read_ints(self):
		return [int(x) for x in self.input().split()]

class Node:

	def __init__(self, data):
		self.data = data
		self.sum = data
		self.rank = 0
		self.parent = self

	def __repr__(self):
		return f'data = {self.data}, sum = {self.sum}, rank = {self.rank}, parent = {self.parent.data}'

class UnionFind:

	def __init__(self):
		self.map = {}

	def makeset(self, index, data):
		self.map[index] = Node(data)

	def find_parent(self, data):
		return self.find(self.map.get(data))

	def find(self, node):
		if node.parent is node:
			return node
		return self.find(node.parent)

	def union(self, left, right):
		left_par = self.find(left)
		right_par = self.find(right)
		if left_par is right_par:
			return
		if left_par.rank >= right_par.rank:
			if left_par.rank == right_par.rank:
				left_par.rank += 1
			right_par.parent = left_par
			left_par.sum += right_par.sum
		else:
			left_par.parent = right_par
			right_par.sum += left_par.sum

def main():
	io = IO()
	n = io.read_int()
	uf = UnionFind()
	arr = io.read_ints()
	for (index, elem) in enumerate(arr):
		uf.makeset(index + 1, elem)
	perm = io.read_ints()
	perm.reverse()
	result = []
	answer = 0
	result.append(answer)
	entry = [-1] * (n + 2)
	for pos in perm[:-1]:
		left_neighbor = pos - 1
		right_neighbor = pos + 1
		if entry[left_neighbor] > -1:
			left_parent = uf.find_parent(left_neighbor)
			node = uf.find_parent(pos)
			uf.union(left_parent, node)
			answer = max(answer, uf.find_parent(pos).sum)
		if entry[right_neighbor] > -1:
			right_parent = uf.find_parent(right_neighbor)
			node = uf.find_parent(pos)
			uf.union(node, right_parent)
			answer = max(answer, uf.find_parent(pos).sum)
		if entry[left_neighbor] == -1 and entry[right_neighbor] == -1:
			answer = max(answer, uf.find_parent(pos).sum)
		entry[pos] = arr[pos - 1]
		result.append(answer)
	for _ in result[::-1]:
		print(_)
main()


from sys import stdin, stdout
import sys
sys.setrecursionlimit(200000)

def main():
	n = int(stdin.readline())
	ar = list(map(int, stdin.readline().split()))
	perm = list(map(int, stdin.readline().split()))
	parent = [i for i in range(n)]
	check = [False] * n
	seg_sum = [ar[i] for i in range(n)]

	def get_parent(index):
		if parent[index] != index:
			stack = []
			curr = index
			while curr != parent[curr]:
				stack.append(curr)
				curr = parent[curr]
			while stack:
				tmp = stack.pop()
				parent[tmp] = curr
		return parent[index]

	def union(index1, index2):
		p1 = get_parent(index1)
		p2 = get_parent(index2)
		if p1 != p2:
			if p1 > p2:
				parent[p1] = p2
				seg_sum[p2] += seg_sum[p1]
			else:
				parent[p2] = p1
				seg_sum[p1] += seg_sum[p2]
	perm.reverse()
	ans_list = [0]
	curr_max = 0
	for i in range(n):
		cid = perm[i] - 1
		if cid - 1 >= 0 and check[cid - 1]:
			union(cid, cid - 1)
		if cid + 1 < n and check[cid + 1]:
			union(cid, cid + 1)
		check[cid] = True
		cp = get_parent(cid)
		curr_max = max(curr_max, seg_sum[cp])
		ans_list.append(curr_max)
	ans_list.reverse()
	ans_list = ans_list[1:]
	for ans in ans_list:
		stdout.write(str(ans))
		stdout.write('\n')
main()


from __future__ import print_function
from itertools import permutations as perm
from collections import *
from sys import stdin
from bisect import *
from heapq import *
from math import *
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
mod = int(1000000000.0) + 7
inf = float('inf')
(n,) = gil()
a = [0] + gil()
for i in range(n + 1):
	a[i] += a[i - 1]
idx = gil()
ans = []
h = [0]
(l, r) = ([0] * (n + 2), [0] * (n + 2))
while idx:
	ans.append(-h[0])
	i = idx.pop()
	(li, ri) = (i - l[i - 1], i + r[i + 1])
	cnt = ri - li + 1
	r[li] = l[ri] = cnt
	rangeSm = a[li - 1] - a[ri]
	heappush(h, rangeSm)
ans.reverse()
print(*ans, sep='\n')


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)


import math, sys, bisect, heapq, os
from collections import defaultdict, Counter, deque
from itertools import groupby, accumulate
from functools import lru_cache
int1 = lambda x: int(x) - 1

def input():
	return sys.stdin.readline().rstrip('\r\n')
aj = lambda : list(map(int, input().split()))

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def Y(c):
	print(['NO', 'YES'][c])

def y(c):
	print(['no', 'yes'][c])

def Yy(c):
	print(['No', 'Yes'][c])
ans = 0

def solve():
	(n,) = aj()
	a = aj()
	p = aj()
	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 ans:
		print(ans.pop())
try:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
except:
	pass
solve()


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()