题目描述

译自 NOISG 2022 Final T5. Fruits

超市通常在不同区域出售水果，每个区域专售一种水果。兔子本森光顾的超市有 $N$ 个区域和 $N$ 种水果。区域编号从 $1$ 到 $N$，每种水果也编号从 $1$ 到 $N$。

第 $i$ 种水果的美味度为 $i$，成本为 $C_i$。保证对于所有 $1 \leq i \leq j \leq N$，$C_i \leq C_j$。 每个 $N$ 个区域需分配一种不同的水果。目前，区域 $j$ 分配的水果类型为 $A_j$。若 $A_j = -1$，则区域 $j$ 为空；否则，区域 $j$ 已分配水果 $A_j$。当所有 $N$ 种水果分配完成后，超市将开业，本森将进入超市购买水果。

本森非常挑剔但又时间紧迫，因此他将按区域编号递增的顺序访问区域。本森的篮子初始为空，当他到达一个区域时，他会比较该区域水果的美味度与篮子中所有水果的美味度。如果篮子为空，或者当前区域水果的美味度高于篮子中所有水果的美味度，本森会将该水果加入篮子。

为了最大化收入，你的任务是分配水果到各个区域，使本森加入篮子的水果成本总和最大化。由于本森时间紧迫，他可能只访问前几个区域后直接前往收银台。帮助计算对于每个 $k$（从 $1$ 到 $N$），在水果分配可针对不同 $k$ 改变的情况下，若本森只访问前 $k$ 个区域，能实现的最大可能收入。

输入格式

程序需从标准输入读取数据。

第一行包含一个正整数 $N$。

第二行包含 $N$ 个整数，第 $i$ 个整数表示 $A_i$。

第三行包含 $N$ 个整数，第 $i$ 个整数表示 $C_i$。

输出格式

程序需向标准输出输出结果。

输出一行，包含 $N$ 个整数，第 $k$ 个整数表示若本森只访问前 $k$ 个区域且水果分配最优时，本森支付的最大成本总和。

5
-1 -1 -1 -1 -1
1 1 1 1 1

1 2 3 4 5

可以将水果按美味度递增顺序排列 $(1, 2, 3, 4, 5)$。本森会拿走他经过的所有水果，因此对于每个 $k$（从 $1$ 到 $5$），本森会拿 $k$ 种水果，总成本为 $k$。

这个样例满足所有子任务的限制。

5
-1 3 -1 -1 -1
1 2 2 2 3

3 4 7 9 9

若本森只访问第 $1$ 个区域，最优分配是将水果 $5$ 放入区域 $1$，成本为 $3$。

若本森只访问前 $2$ 个区域，最优分配是将水果 $2$ 放入区域 $1$，水果 $3$ 放入区域 $2$，成本为 $2 + 2 = 4$。

若本森只访问前 $3$ 个区域，最优分配是将水果 $2$ 放入区域 $1$，水果 $3$ 放入区域 $2$，水果 $5$ 放入区域 $3$，成本为 $2 + 2 + 3 = 7$。

若本森访问前 $4$ 个或全部 $5$ 个区域，最优分配顺序为 $2, 3, 4, 5, 1$，成本为 $2 + 2 + 2 + 3 = 9$。

这个样例满足子任务 $1, 3, 4, 6$ 的限制。

13
-1 -1 5 6 -1 -1 7 11 -1 -1 10 -1 -1
1 1 1 1 1 1 1 1 1 1 1 1 1

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

这个样例满足子任务 $3, 4, 5, 6$ 的限制。

10
-1 -1 -1 -1 5 -1 -1 -1 9 -1
5 11 24 27 35 60 72 81 91 92

92 173 245 305 305 332 356 367 406 498

这个样例满足子任务 $3, 4, 6$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N \leq 400000$
• $1 \leq A_j \leq N$ 或 $A_j = -1$
• $1 \leq C_i \leq 10^9$
• 对于所有 $1 \leq i < j \leq N$，$C_i \leq C_j$

详细子任务附加限制及分值如下表所示：