#P18112. Dynamic Adjustment

Dynamic Adjustment

Dynamic Adjustment

对整数数组 a1,…,ama_1,\ldots,a_m,定义

$$f(a)=\min_{b_1\le\cdots\le b_m}\sum_{j=1}^{m}|a_j-b_j|,$$

其中 bjb_j 可以是任意整数,不要求属于原数组。

给定数组 x1,…,xnx_1,\ldots,x_n 和位置排列 p1,…,pnp_1,\ldots,p_n。对每个 i=1,…,ni=1,\ldots,n,把位置 p1,…,pip_1,\ldots,p_i 按从小到大排序为 q1<⋯<qiq_1<\cdots<q_i,形成子序列 a=(xq1,…,xqi)a=(x_{q_1},\ldots,x_{q_i})。求这 nn 个子序列各自的 f(a)f(a)。

注意,子序列按原数组位置排列,不是按加入时间,也不是按数值排序。

输入格式

第一行整数 nn,1≤n≤2000001\le n\le200000。

第二行 nn 个整数 xix_i,−109≤xi≤109-10^9\le x_i\le10^9。

第三行 1,…,n1,\ldots,n 的一个排列 pp。

输出格式

输出 nn 个整数,第 ii 个是前 ii 个位置加入后的最小修改代价。

样例1

5
5 4 3 2 1
1 2 3 4 5
0 1 2 4 6

样例2

3
3 2 1
1 3 2
0 2 2

样例2的子序列依次为 [3][3]、[3,1][3,1]、[3,2,1][3,2,1]。后两者修改成常值数组都能达到代价2。