Here, we simply call “the card with integer \(v\) written on it” as “integer \(v\).”

First, we find how many times each integer occurs in the initial hand. Specifically, we find the sequence \(((v_0, f_0), (v_1, f_1), (v_2, f_2), \ldots, (v_{k-1}, f_{k-1}))\), expressing that “integer \(v_i\) occurs \(f_i\) times.” Here, without loss of generality, we assume that \(f_0, f_1, \ldots\), and \(f_{k-1}\) are all positive, and \(v_0 \lt v_1 \lt \cdots \lt v_{k-1}\). This sequence can be found in a total of \(O(N \log N)\) time using an associative array.

When it comes to minimizing the sum of the remaining integers in hand, we assume that Takahashi always put the same integer as the one we have put last time as much as possible. Therefore, we can always uniquely determine the second and later cards to put, so the only choice left to him is the first card to put.

If every integer between \(0\) and \(M-1\) occurs in the initial hand, that is, if \(k=M\), then we can put all the cards in hand regardless of the first card. So, in this case we should output \(0\).

Hereinafter we assume that \(k \leq M-1\).

Let us denote by \(s_i\) “the sum of integers in the final hand when the first card is \(v_i\),” and try finding \(s_0, s_1, \ldots, s_{k-1}\). When the first card is \(v_i\),

• if \(v_{(i+1) \bmod k} \neq (v_i + 1) \bmod M\), then, starting from the initial hand (of sum \(\sum_{j = 0}^k v_jf_j\)), he can just put the card \(v_i\) \(f_i\) times, and that’s all, so \(s_i = (\sum_{j = 0}^k v_jf_j) - v_if_i\).
• if \(v_{(i+1) \bmod k} = (v_i + 1) \bmod M\), then, he put the card \(v_i\) \(f_i\) cards, then resume the operation as if the first card were integer \((v_i + 1) \bmod M\), so \(s_i = s_{(i+1) \bmod k} - v_if_i\).

Therefore, starting from some \(p\) such that \(v_{(p+1) \bmod k} \neq (v_p + 1) \bmod M\), we compute each \(s_i\) for each \(i = p, p-1, p-2, \ldots, 1, 0, k-1, k-2, \ldots, p+1\) in this order, spending a total of \(O(N)\) time. The value to output is \(\min \lbrace s_0, s_1, \ldots, s_{k-1} \rbrace\).

Therefore, this problem can be solved in a total of \(O(N \log N)\) time.

The following is a sample code in C++ language.

#include <iostream>
#include <map>
#include <utility>
#include <vector>
using namespace std;
typedef long long ll;

ll s[200005];

int main(void)
{
  ll n, m, a, sum = 0; 
  map<ll, ll> mp;
  
  cin >> n >> m;
  for(int i = 1; i <= n; i++){
    cin >> a;
    mp[a]++;
    sum += a;
  }  
  vector<pair<ll, ll>> vec;
  for(auto p : mp) vec.push_back(p);
  int k = vec.size();
  
  if(k == m){
    cout << 0 << endl;
    return 0;
  }
  
  int p;
  for(int i = 0; i < k; i++){
    if(vec[(i+1)%k].first != (vec[i].first+1)%m){
      p = i;
      break;
    }
  }
  
  for(int i = 0; i < k; i++){
    int j = (p-i+k)%k;
    s[j] = sum;
    if(vec[(j+1)%k].first == (vec[j].first+1)%m) s[j] = s[(j+1)%k];
    s[j] -= vec[j].first * vec[j].second;
  }
  
  ll ans = sum;
  for(int i = 0; i < k; i++) ans = min(ans, s[i]);
  cout << ans << endl;
  
  return 0;
}