과일

슈퍼마켓에서는 보통 과일을 구역별로 진열하며, 각 구역에는 한 종류의 과일만 놓여 있다. Benson 토끼가 방문한 슈퍼마켓에는 $N$개의 구역과 $N$종류의 과일이 있다. 구역은 $1$번부터 $N$번까지 번호가 붙어 있고, 과일도 $1$번부터 $N$번까지 번호가 붙어 있다.

$i$번째 과일의 맛은 $i$이고 비용은 $C_i$이다. 모든 $1 \le i < j \le N$에 대해 $C_i \le C_j$가 보장된다.

N개의 구역에는 각각 서로 다른 종류의 과일이 하나씩 배정되어야 한다. $j$번 구역에는 현재 과일 $A_j$가 놓여 있다. $A_j = -1$이면 $j$번 구역은 비어 있다. 그렇지 않으면 과일 $A_j$가 이미 $j$번 구역에 배정되어 있다. 과일 N개를 모두 배정하면 슈퍼마켓이 문을 열고, Benson이 들어와 과일을 산다.

Benson은 까다롭지만 급하기 때문에 구역을 번호 순서대로 방문한다. 그의 바구니는 처음에 비어 있다. 구역에 도착하면 그 구역 과일의 맛을 바구니에 있는 모든 과일의 맛과 비교한다. 바구니가 비어 있거나, 현재 과일이 바구니의 다른 모든 과일보다 맛이 좋으면 Benson은 그 과일을 바구니에 담는다.

Benson이 바구니에 담는 과일 비용의 합이 최대가 되도록 과일을 배정해야 한다. Benson은 서두르기 때문에 처음 몇 개의 구역만 방문하고 곧바로 계산대로 갈 수도 있다. $1$부터 $N$까지의 각 $k$에 대해, Benson이 처음 $k$개의 구역만 방문할 때 얻을 수 있는 최대 수익을 구하라. 과일 배치는 $k$마다 다르게 정해도 된다.

첫 줄에는 양의 정수 $N$이 주어진다.

둘째 줄에는 $N$개의 정수가 주어지며, $i$번째 정수는 $A_i$이다.

셋째 줄에는 $N$개의 정수가 주어지며, $i$번째 정수는 $C_i$이다.

한 줄에 $N$개의 정수를 출력한다. $k$번째 정수는 과일을 최적으로 배정했을 때, Benson이 처음 $k$개의 구역만 방문하면서 지불하는 비용 합의 최댓값이다.

• $1 \le N \le 400\,000$
• $1 \le A_j \le N$ 또는 $A_j = -1$
• $1 \le C_i \le 10^9$
• 모든 $1 \le i < j \le N$에 대해 $C_i \le C_j$