AT_donuts_2015_4 ドーナツの箱詰め

[problemUrl]: https://atcoder.jp/contests/donuts-2015/tasks/donuts_2015_4 ドーナツ屋の店員の須藤なつきさんはドーナツの箱詰めの担当です。なつきさんは今、$ K $ 個のドーナツを $ N $ 個の箱に箱詰めしようとしています。箱 $ i\ (1\ ≦\ i\ ≦\ N) $ の体積は $ C_i $ で、どの箱もドーナツを $ 1 $ つ入れることができます。 なつきさんは全ての箱を使いたいと思っています。しかし、ドーナツの個数よりも箱の個数の方が多いため、箱の中に箱を入れ子にすることによって箱を使い切ることにしました。各箱の中には、ドーナツまたは箱のいずれか一方を必ずちょうど $ 1 $ 個入れることにしました。箱 $ i $ には箱 $ i $ よりも体積が小さい箱を入れることができます。また、中に入れる箱の中にさらに箱やドーナツが入っていた場合でもその箱は $ 1 $ 個として数えます。箱 $ i $ の中に箱 $ j $ を入れた場合には、箱 $ i $ と箱 $ j $ の間に $ C_{i}\ -\ C_{j} $ の量の緩衝材を入れなければなりません。このとき、必要な緩衝材の量の和の最小値を求めてください。 また、なつきさんはとても不器用なので箱詰めの途中で箱を潰してしまうことがあります。なつきさんが箱を潰すごとに、その時点で残っている箱を全て使って箱詰めをするときに必要な緩衝材の量の和の最小値を求めてください。なつきさんは合計 $ Q $ 個の箱を潰し、$ i $ 個目に潰した箱は箱 $ D_i $ です。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ C_1 $ $ C_2 $ ... $ C_N $ $ Q $ $ D_1 $ $ D_2 $ : $ D_Q $ - $ 1 $ 行目には、$ 2 $ つの整数 $ N\ (1\ ≦\ N\ ≦\ 200,000),\ K\ (1\ ≦\ K\ ≦\ N) $ が空白区切りで与えられる。これは、はじめに箱が $ N $ 個とドーナツが $ K $ 個あるということを表す。 - $ 2 $ 行目には、箱の体積を表す $ N $ 個の整数が空白区切りで与えられる。このうち $ i $ 番目の整数 $ C_i\ (1\ ≦\ C_i\ ≦\ 200,000) $ は、箱 $ i $ の体積を表す。ただし、$ p\ \neq\ q $ のとき $ C_p\ \neq\ C_q $ であることが保証される。 - $ 3 $ 行目には、なつきさんが潰した箱の個数を表す整数 $ Q\ (0\ ≦\ Q\ ≦\ N-K) $ が与えられる。 - $ 4 $ 行目からの $ Q $ 行には、なつきさんが潰した箱の情報が与えられる。このうち $ i $ 行目には、整数 $ D_i\ (1\ ≦\ D_i\ ≦\ N) $ が与えられる。これは、なつきさんが $ i $ 個目に潰した箱が箱 $ D_i $ であることを表す。ただし、$ p\ \neq\ q $ のとき $ D_p\ \neq\ D_q $ であることが保証される。

出力は $ Q+1 $ 行からなる。$ 1 $ 行目には、$ N $ 個の箱を全て使って箱詰めをするときに必要な緩衝材の量の和の最小値を出力し、$ 2 $ 行目から $ Q+1 $ 行目までのうち $ i\ (1\ ≦\ i\ ≦\ Q) $ 行目には、$ i $ 個目までの箱を潰した時点で残っている箱を全て使って箱詰めをするときに必要な緩衝材の量の和の最小値を出力せよ。出力の末尾にも改行を入れること。

### 部分点 この問題には部分点が設定されている。 - $ Q\ =\ 0 $ かつ $ K\ =\ 2 $ を満たすデータセット $ 1 $ に正解した場合は、$ 15 $ 点が与えられる。 - $ Q\ =\ 0 $ を満たすデータセット $ 2 $ に正解した場合は、上記とは別に $ 25 $ 点が与えられる。 - $ K\ =\ 2 $ を満たすデータセット $ 3 $ に正解した場合は、上記とは別に $ 30 $ 点が与えられる。 ### Sample Explanation 1 このケースでは図のような箱詰めの仕方をすると必要な緩衝材の量が $ 1 $ となり最小となります。青い部分は緩衝材を入れる部分を表しています。 !\[\](http://donuts-2015.contest.atcoder.jp/img/other/donuts\_2015/figD1.png)また、このケースではなつきさんは箱を $ 1 $ 個も潰しません。 ### Sample Explanation 2 このケースでは図のような箱詰めの仕方をすると良いです。青い部分は緩衝材を入れる部分を表しています。 !\[\](http://donuts-2015.contest.atcoder.jp/img/other/donuts\_2015/figD2.png)