题目描述

超市里通常有专门的一区卖水果。

兔子 $\text{Benson}$ 常去的超市一共有 $N$ 个柜台用来卖 $N$ 种水果。柜台编号从 $1 \sim N$，水果编号从 $1 \sim N$。第 $i$ 种水果的美味度是 $i$，购买需要花费 $C_i$ 元。保证对于所有的 $1 \le i < j \le N$，有 $C_i \le C_j$。

每一个柜台都只买一种水果，每一种水果都有且仅有一个柜台售卖。现在，工作人员规定了每个柜台卖哪一种水果。第 $i$ 个柜台卖第 $A_i$ 种水果。如果 $A_i=-1$，则表示这个柜台还没有确定卖什么。

当所有柜台的水果都摆放好，$\text{Benson}$ 就会进店抢购。他会按照 $1 \sim N$ 的顺序去这些柜台。当他到了一个柜台，如果他的购物车里还是空的，或当前柜台水果的美味度大于所有他购物车里的水果，那么他就会购买这种水果，将其放进购物车中。

现在你需要让商店赚到最多的钱。你需要计算怎么来摆放那些 $A_i=-1$ 的柜台使得利润最大化。由于 $\text{Benson}$ 很赶时间，他可能不会逛完所有柜台，所以你需要对于所有的 $1 \le k \le N$ 计算如果 $\text{Benson}$ 只逛第 $1 \sim k$ 个柜台，那么这些柜台应该如何摆放最优。

输入格式

第一行，一个正整数 $N$；

第二行 $N$ 个整数，表示 $A_i$；

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

输出格式

一行 $N$ 个整数，第 $k$ 个表示如果 $\text{Benson}$ 只逛前 $k$ 个柜台且水果按照最优方案摆放，商店可获得的最大钱数。

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

1 2 3 4 5

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

3 4 7 9 9

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

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

提示

【数据范围】

对于 $100\%$ 的数据，$1 \le N \le 400000,1 \le A_j \le N$ 或 $A_j=-1,1 \le C_i \le 10^9$。