AT_agc077_f [AGC077F] Two Types of Tasks

$ 1 $ から $ N $ までの番号がついた $ N $ 個の仕事があり，これらを $ N $ 日間で終わらせたいです． $ 1 $ 日にちょうど $ 1 $ つの仕事を行います． 仕事 $ i $ は， $ L_i $ 日目から $ R_i $ 日目までのいずれかの日に行うことができます． ここで， $ L_i,R_i $ に関して，以下の条件が満たされることが保証されます． - $ 1 \leq L_i \leq i \leq R_i \leq N $ - $ 1 \leq L_1 \leq L_2 \leq \cdots \leq L_N \leq N $ - $ 1 \leq R_1 \leq R_2 \leq \cdots \leq R_N \leq N $ 特に最初の条件より， $ N $ 個の仕事を $ N $ 日間で終わらせることが可能だとわかります． また，それぞれの仕事には `L` または `R` のタイプが定まっています． 最初，すべての仕事はタイプ `R` です． 仕事を行うコストを以下のように定義します． - 仕事 $ i $ を $ x_i $ 日目に行うとする．仕事 $ i $ がタイプ `L` ならコストを $ x_i-L_i $ と定め，タイプ `R` ならコストを $ R_i-x_i $ と定める． 今から，仕事のタイプを `L` に変更するクエリが $ N $ 回来ます． $ i $ 番目のクエリでは，仕事 $ P_i $ のタイプを `L` に変更します． 各 $ k=0,1,\ldots,N $ に対して，次の問題を解いて下さい． - 最初の $ k $ 回のクエリを処理した状態を考える． この時， $ N $ 個の仕事のコストの総和としてあり得る最小値を求めよ．

入力は以下の形式で標準入力から与えられる． > $ N $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ \vdots $ $ L_N $ $ R_N $ $ P_1 $ $ P_2 $ $ \ldots $ $ P_N $

各 $ k=0,1,2,\ldots,N $ に対する答えをこの順に空白区切りで出力せよ．

### Sample Explanation 1 各 $ k $ に対する最適な仕事のやり方は以下のとおりです． - $ k=0 $ : 仕事 $ 1,2,3 $ をそれぞれ $ 1,2,3 $ 日目に行う．コストの総和は $ (3-1)+(3-2)+(3-3)=3 $ になる． - $ k=1 $ : 仕事 $ 1,2,3 $ をそれぞれ $ 2,1,3 $ 日目に行う．コストの総和は $ (3-2)+(1-1)+(3-3)=1 $ になる． - $ k=2 $ : 仕事 $ 1,2,3 $ をそれぞれ $ 1,2,3 $ 日目に行う．コストの総和は $ (1-1)+(2-1)+(3-3)=1 $ になる． - $ k=3 $ : 仕事 $ 1,2,3 $ をそれぞれ $ 1,2,3 $ 日目に行う．コストの総和は $ (1-1)+(2-1)+(3-2)=2 $ になる． ### Constraints - $ 1 \leq N \leq 10^6 $ - $ 1 \leq L_i \leq i \leq R_i \leq N $ - $ 1 \leq L_1 \leq L_2 \leq \cdots \leq L_N \leq N $ - $ 1 \leq R_1 \leq R_2 \leq \cdots \leq R_N \leq N $ - $ (P_1,P_2,\ldots,P_N) $ は $ (1,2,\ldots,N) $ の順列 - 入力される数値は全て整数