Given an increasing weight array (c) and a partially determined permutation, the task is to complete the permutation such that the sum of weights for all prefixes of length (k) containing maximum values is maximized. For each (k), we compute the optimal result.

A direct approach involves dynamic programming with state (dp_{i,j}) representing the maximum weight when considering the first (i) elements with their maximum being (j). Transition occurs naturally through prefix maximum updates. To ensure validity, the condition (s_i \leq t_j) must hold where (s_i) counts unfixed positions among the first (i) slots and (t_j) counts unused numbers from (1) to (j).

To simplify transitions, let (b) represent sorted unused values. Define two states: (f_{i,j}) denotes maximum weight when the first (i) elements have maximum value (b_j), and (g_i) represents the case when the maximum is already fixed at some known value (mx).

The key insight lies in observing monotonic properties of (f'i = f_i - c{b_j}). This allows transforming complex update operations into simpler forms suitable for optimization via data structures.

Using a deque-based structure with lazy propagation efficiently maintains required operations:

• Querying head/tail values
• Removing prefix segments
• Applying global max operations equivalent to prefix assignments due to monotonicity
• Shifting values based on cumulative weights

Lazy tags store cumulative shifts derived from previous segment contributions. Prefix assignment uses color-count amortization by binary search with in single segments followed by deque modifications.

Below is an optimized implementation achieving (O(n \log n)) complexity:

#include <algorithm>
#include <cstdio>
#include <deque>
using namespace std;

const int MAXN = 400003;
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int input() {
    char c = getchar();
    int num = 0;
    bool neg = false;
    while (c < '0' || c > '9')
        neg |= (c == '-'), c = getchar();
    do
        num = num * 10 + (c ^ 48), c = getchar();
    while (c >= '0' && c <= '9');
    return neg ? -num : num;
}

int total, unknown_count, current_limit;
int perm[MAXN], available_values[MAXN], weights[MAXN], adjusted_weights[MAXN];
bool occupied[MAXN];
ll prefix_sums[MAXN];

inline void maximize(ll &target, ll candidate) {
    if (target < candidate)
        target = candidate;
}

struct SegmentInfo {
    int length, timestamp;
    ll base_value;
    SegmentInfo(int l, int ts, ll bv) : length(l), timestamp(ts), base_value(bv) {}
};

deque<SegmentInfo> segments;

ll get_head_value() {
    if (segments.empty()) return -INF;
    auto &front_segment = segments.front();
    ll adjustment = prefix_sums[current_limit - (unknown_count - front_segment.timestamp)] 
                   - prefix_sums[current_limit];
    return front_segment.base_value + adjustment;
}

ll get_tail_value() {
    if (segments.empty()) return -INF;
    auto &back_segment = segments.back();
    ll adjustment = prefix_sums[unknown_count - (unknown_count - back_segment.timestamp)] 
                   - prefix_sums[unknown_count];
    return back_segment.base_value + adjustment;
}

void remove_head() {
    if (!--segments.front().length)
        segments.pop_front();
}

void remove_tail() {
    if (!--segments.back().length)
        segments.pop_back();
}

int main() {
    total = input();
    for (int idx = 1; idx <= total; ++idx) {
        perm[idx] = input();
        if (~perm[idx])
            occupied[perm[idx]] = true;
    }

    for (int idx = 1; idx <= total; ++idx) {
        weights[idx] = input();
        if (!occupied[idx]) {
            adjusted_weights[++unknown_count] = weights[idx];
            available_values[unknown_count] = idx;
        }
    }

    int max_known = 0;
    for (int idx = unknown_count; ~idx; --idx)
        prefix_sums[idx] = prefix_sums[idx + 1] + adjusted_weights[idx];

    current_limit = 1;
    segments.emplace_back(unknown_count, 0, -INF);
    ll current_max = 0;

    for (int pos = 1; pos <= total; ++pos) {
        if (~perm[pos]) {
            if (max_known < perm[pos]) {
                ll temp_result = current_max;
                while (current_limit <= unknown_count && available_values[current_limit] < perm[pos]) {
                    maximize(temp_result, get_head_value() + adjusted_weights[current_limit]);
                    remove_head();
                    ++current_limit;
                }
                if (current_limit > unknown_count)
                    current_max = temp_result + weights[perm[pos]];
                else
                    current_max = -INF;
                max_known = perm[pos];
            }
        } else {
            ll prev_head = get_head_value();
            ++unknown_count;
            if (!segments.empty()) {
                remove_tail();
                segments.emplace_front(1, unknown_count, prev_head);
            }

            int removed_length = 0;
            while (!segments.empty()) {
                int right_bound = current_limit + segments.front().length - 1;
                int time_offset = unknown_count - segments.front().timestamp;
                ll adjusted_val = segments.front().base_value + prefix_sums[right_bound - time_offset] - prefix_sums[right_bound];
                if (adjusted_val > current_max)
                    break;
                removed_length += segments.front().length;
                current_limit += segments.front().length;
                segments.pop_front();
            }

            if (!segments.empty()) {
                int left_search = current_limit;
                int right_search = current_limit + segments.front().length;
                int time_diff = unknown_count - segments.front().timestamp;
                while (left_search < right_search) {
                    int mid_point = (left_search + right_search) >> 1;
                    ll test_value = segments.front().base_value + prefix_sums[mid_point - time_diff] - prefix_sums[mid_point];
                    if (test_value <= current_max)
                        left_search = mid_point + 1;
                    else
                        right_search = mid_point;
                }
                removed_length += right_search - current_limit;
                segments.front().length -= right_search - current_limit;
                current_limit = right_search;
            }

            if (removed_length)
                segments.emplace_front(removed_length, unknown_count, current_max), current_limit -= removed_length;
            if (unknown_count > current_limit)
                remove_head(), ++current_limit;
        }
        printf("%lld ", max(current_max, get_tail_value() + adjusted_weights[unknown_count]));
    }
    putchar('\n');
    return 0;
}