题目描述

给定一个长度为 $n$ 的序列 $a_1\cdots a_n$ 以及一个序列 $b_1\cdots b_n$。

定义一个区间 $[l,r]$ 的权值 $w(l,r)$ 为

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

其中 $[\text{cond}]$ 当且仅当 $\text{cond}$ 为真时 $=1$ 否则 $=0$。

对于每一个 $p=1,2\cdots n$，请你将 $1\cdots p$ 划分成若干段，使得每段的权值之和最小，形式化的，你要找出若干下标 $x_0\cdots x_k$，使得：

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

在此基础上，使得 $\sum\limits_{i=1}^{k}w(x_{i-1}+1,x_i)$ 最小。

输入格式

第一行一个整数 $n$ 代表序列长度。

第二行 $n$ 个整数描述一个长度为 $n$ 的序列 $a_1\cdots a_n$。

第三行 $n$ 个整数描述一个长度为 $n$ 的序列 $b_1\cdots b_n$。

输出格式

一行 $n$ 个整数依次代表每一个前缀的答案。

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

2 2 3 5 5 6

提示

• 对于 $20\%$ 的数据，$n\leq 5000$。
• 对于 $50\%$ 的数据，$n\leq 10^5$。
• 对于 $100\%$ 的数据，$n\leq 5\times 10^5,1\leq a_i\leq n,0\leq b_i\leq 10^9$。