Maximizing Supermarket Revenue

A supermarket has N counters selling N distinct fruits. Fruit i has a deliciousness of i and costs \(C_i\) dollars. It is guaranteed that \(C_1 \le C_2 \le \cdots \le C_N\). Each fruit appears exactly once and each counter sells exactly one fruit. The store has already fixed the fruit sold at each counter in an array \(A\) of length \(N\), where the counter i sells fruit \(A_i\). If \(A_i = -1\), the fruit at that counter is not yet decided. The final assignment must be a permutation of \(\{1,2,\dots,N\}\; (i.e., each fruit is used exactly once).

Benson, a swift rabbit, visits the counters in order from 1 to \(N\). He starts with an empty shopping cart. At each counter, if his shopping cart is empty or the fruit sold has a deliciousness greater than every fruit already in his cart, then he purchases that fruit (adding it to his cart). In other words, he buys the fruit at counter \(i\) if \(X_i > \max\{X_1, X_2, \dots, X_{i-1}\}\), where \(X_i\) is the fruit (its number) placed at counter \(i\).

Your task is to determine how to assign fruits to those counters with \(A_i = -1\) in order to maximize the store's revenue. The revenue is the sum of \(C_x\) for every fruit \(x\) that Benson buys. Because Benson might only visit the first \(k\) counters for some \(1 \le k \le N\), you need to consider the optimal assignment and compute the maximum revenue for every prefix \(k\). For each \(k\) (from 1 to \(N\)), find the maximum revenue the store can earn if Benson only visits counters \(1,2,\dots,k\>.

inputFormat

The first line contains a single integer \(N\) denoting the number of counters (and fruits).
The second line contains \(N\) space‐separated integers \(C_1, C_2, \dots, C_N\) representing the cost of each fruit, with \(C_1 \le C_2 \le \cdots \le C_N\).
The third line contains \(N\) space‐separated integers \(A_1, A_2, \dots, A_N\), where \(A_i = -1\) indicates that the fruit at counter i is not fixed, and otherwise \(A_i\) is the fruit assigned to counter i.

outputFormat

Output \(N\) lines. The \(k\)th line (for \(1 \le k \le N\)) should contain a single integer — the maximum revenue the store can earn if Benson only visits the first \(k\) counters, assuming an optimal assignment of fruits for counters with \(A_i = -1\).

sample

3
1 2 3
-1 -1 -1

1
3
6