Problem Description

You are given a sequence $a_1 \cdots a_n$ of length $n$ and a sequence $b_1 \cdots b_n$.

Define the weight $w(l,r)$ of an interval $[l,r]$ as

$$b_r+\sum\limits_{i=l}^r\sum\limits_{j=i+1}^r[a_i=a_j]$$

where $[\text{cond}] = 1$ if and only if $\text{cond}$ is true, otherwise $= 0$.

For each $p = 1,2,\cdots n$, you need to partition $1 \cdots p$ into several segments so that the sum of the weights of all segments is minimized. Formally, you need to find some indices $x_0 \cdots x_k$ such that:

• $x_1 = 0, x_k = p$.
• $\forall i = 0,1,\cdots k-1, x_i < x_{i+1}$.

Based on this, minimize $\sum\limits_{i=1}^{k} w(x_{i-1}+1,x_i)$.

Input Format

The first line contains an integer $n$, representing the length of the sequences.

The second line contains $n$ integers describing the sequence $a_1 \cdots a_n$ of length $n$.

The third line contains $n$ integers describing the sequence $b_1 \cdots b_n$ of length $n$.

Output Format

Output one line with $n$ integers, where the $i$-th integer is the answer for the prefix $1 \cdots i$.

6
1 2 1 1 2 1
2 2 2 2 2 2

2 2 3 5 5 6

Hint

Constraints

• For $20\%$ of the testdata, $n \leq 5000$.
• For $50\%$ of the testdata, $n \leq 10^5$.
• For $100\%$ of the testdata, $n \leq 5\times 10^5, 1 \leq a_i \leq n, 0 \leq b_i \leq 10^9$.

Translated by ChatGPT 5