[ABC277D] Takahashi's Solitaire

【题面翻译】 给定 $n$ 张牌，每张牌上有一个数字 $a_i$。 你要先选一张牌放在桌子上。假设当前最后一张放置的牌为 $x$，接下来，你每次只能放写着 $x$ 或 $(x + 1) \bmod m$ 的牌。 一直操作下去。你需要让你手上剩下的牌的总和**最小**。 translated by @[liangbowen](https://www.luogu.com.cn/user/367488). 【输入格式】 第一行两个数 $n$，$m$。 接下来 $n$ 个数，表示卡牌上的数字 $a_i$。 【输出格式】 输出最小和值。 【数据范围】 $1 \le n \le 2 \times 10^5$ $2 \le m \le 10^9$ 保证 $0 \le a_i < m$。

[problemUrl]: https://atcoder.jp/contests/abc277/tasks/abc277_d 高橋君は $ N $ 枚のカードを手札として持っています。 $ i\ =\ 1,\ 2,\ \ldots,\ N $ について、$ i $ 番目のカードには非負整数 $ A_i $ が書かれています。 高橋君は、まず手札から好きなカードを $ 1 $ 枚選んで、テーブルの上に置きます。 その後、高橋君は好きな回数（ $ 0 $ 回でも良い）だけ、下記の操作を繰り返します。 - 最後にテーブルの上に置いたカードに書かれた整数を $ X $ とする。手札に整数 $ X $ または整数 $ (X+1)\bmod\ M $ が書かれたカードがあれば、そのうち好きなものを $ 1 $ 枚選んで、テーブルの上に置く。ここで、$ (X+1)\bmod\ M $ は $ (X+1) $ を $ M $ で割ったあまりを表す。 最終的に手札に残ったカードに書かれている整数の総和としてあり得る最小値を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

答えを出力せよ。

9 7
3 0 2 5 5 3 0 6 3

11

1 10
4

0

20 20
18 16 15 9 8 8 17 1 3 17 11 9 12 11 7 3 2 14 3 12

99

### 制約 - $ 1\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 2\ \leq\ M\ \leq\ 10^9 $ - $ 0\ \leq\ A_i\ \lt\ M $ - 入力はすべて整数 ### Sample Explanation 1 高橋君が、まず $ 4 $ 番目のカード（書かれた整数は $ 5 $ ）をテーブルの上に置き、その後、以下の手順で操作を行う場合を考えます。 - $ 5 $ 番目のカード（書かれた整数は $ 5 $ ）をテーブルの上に置く。 - $ 8 $ 番目のカード（書かれた整数は $ 6 $ ）をテーブルの上に置く。 - $ 2 $ 番目のカード（書かれた整数は $ 0 $ ）をテーブルの上に置く。 - $ 7 $ 番目のカード（書かれた整数は $ 0 $ ）をテーブルの上に置く。 このとき、最終的に手札に残ったカードは、$ 1,\ 3,\ 6,\ 9 $ 枚目のカードであり、それらに書かれた整数の総和は $ 3\ +\ 2\ +\ 3\ +3\ =\ 11 $ です。 これが、最終的に手札に残ったカードに書かれている整数の総和としてあり得る最小値です。