Problem Description

Natsuki Sudo, a clerk at a donut shop, is in charge of packing donuts. Natsuki is currently trying to pack $ K $ donuts into $ N $ boxes. The volume of box $i\ (1\ ≦\ i\ ≦\ N)$ is $ C_i $, and each box can hold exactly one donut.

Natsuki wants to use all the boxes. However, since there are more boxes than donuts, she decided to nest boxes inside each other to use all the boxes. Each box must contain exactly one item, either a donut or another box. A box $ i $ can contain a box $ j $ if the volume of box $ j $ is smaller than that of box $ i $. If a box contains another box or donut, it counts as one item. If box $ i $ contains box $ j $, a buffer material of amount $C_{i}\ -\ C_{j}$ must be placed between them. Find the minimum total amount of buffer material needed.

Additionally, Natsuki is very clumsy and may crush boxes during the packing process. For each box she crushes, determine the minimum total amount of buffer material needed to pack the remaining boxes with the remaining donuts. Natsuki will crush a total of $ Q $ boxes, and the $ i $th box she crushes is box $ D_i $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ K $ $ C_1 $ $ C_2 $ ... $ C_N $ $ Q $ $ D_1 $ $ D_2 $ : $ D_Q $

• The first line contains two integers $N\ (1\ ≦\ N\ ≦\ 200,000),\ K\ (1\ ≦\ K\ ≦\ N)$, representing the initial number of boxes and donuts, respectively.
• The second line contains $ N $ integers separated by spaces, where the $ i $th integer $C_i\ (1\ ≦\ C_i\ ≦\ 200,000)$ represents the volume of box $ i $. It is guaranteed that $C_p\ \neq\ C_q$ when $p\ \neq\ q$.
• The third line contains an integer $Q\ (0\ ≦\ Q\ ≦\ N-K)$, representing the number of boxes Natsuki will crush.
• The next $ Q $ lines contain the information about the crushed boxes. The $ i $th line contains an integer $D_i\ (1\ ≦\ D_i\ ≦\ N)$, representing that Natsuki crushed box $ D_i $ as the $ i $th box. It is guaranteed that $D_p\ \neq\ D_q$ when $p\ \neq\ q$.

Output Format

The output consists of $ Q+1 $ lines. The first line should contain the minimum total amount of buffer material needed to pack all $ N $ boxes. For each $i\ (1\ ≦\ i\ ≦\ Q)$, the $ i+1 $th line should contain the minimum total amount of buffer material needed to pack the remaining boxes after Natsuki has crushed $ i $ boxes. Ensure to include a newline at the end of the output.

Sample Input and Output

Sample Input #1

5 4
1 9 3 7 4
0

Sample Output #1

1

Sample Input #2

4 2
6 5 10 2
2
3
1

Sample Output #2

4
1
0

Sample Input #3

7 3
2 12 3 13 7 17 1
4
4
3
1
6

Sample Output #3

7
6
6
5
0

Notes/Hints

Partial Points

This problem has partial points.

• If you solve dataset 1 where $Q\ =\ 0$ and $K\ =\ 2$, you will be awarded 15 points.
• If you solve dataset 2 where $Q\ =\ 0$, you will be awarded an additional 25 points.
• If you solve dataset 3 where $K\ =\ 2$, you will be awarded an additional 30 points.

见题面 Input 部分

见题面 Output 部分