AT_agc077_f [AGC077F] Two Types of Tasks

There are $ N $ jobs numbered $ 1 $ through $ N $ , and you want to complete them over $ N $ days. You perform exactly one job per day. Job $ i $ can be performed on any day from day $ L_i $ through day $ R_i $ . Here, the following conditions are guaranteed to hold for $ L_i $ and $ 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 $ Particularly, from the first condition, it follows that it is possible to complete all $ N $ jobs over $ N $ days. Furthermore, each job has a type of `L` or `R`. Initially, all jobs are of type `R`. The cost of performing a job is defined as follows: - Suppose job $ i $ is performed on day $ x_i $ . If job $ i $ is of type `L`, the cost is defined as $ x_i-L_i $ ; if it is of type `R`, the cost is defined as $ R_i-x_i $ . From now on, there will be $ N $ queries that change the type of a job to `L`. In the $ i $ -th query, the type of job $ P_i $ is changed to `L`. For each $ k=0,1,\ldots,N $ , solve the following problem: - Consider the state after processing the first $ k $ queries. Find the minimum possible total cost of all $ N $ jobs.

The input is given from Standard Input in the following format: > $ N $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ \vdots $ $ L_N $ $ R_N $ $ P_1 $ $ P_2 $ $ \ldots $ $ P_N $

For each $ k=0,1,2,\ldots,N $ , output the answer in this order, separated by spaces.

### Sample Explanation 1 An optimal schedule for each $ k $ is as follows: - $ k=0 $ : Perform jobs $ 1,2,3 $ on days $ 1,2,3 $ respectively. The total cost is $ (3-1)+(3-2)+(3-3)=3 $ . - $ k=1 $ : Perform jobs $ 1,2,3 $ on days $ 2,1,3 $ respectively. The total cost is $ (3-2)+(1-1)+(3-3)=1 $ . - $ k=2 $ : Perform jobs $ 1,2,3 $ on days $ 1,2,3 $ respectively. The total cost is $ (1-1)+(2-1)+(3-3)=1 $ . - $ k=3 $ : Perform jobs $ 1,2,3 $ on days $ 1,2,3 $ respectively. The total cost is $ (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) $ is a permutation of $ (1,2,\ldots,N) $ . - All input values are integers.