I came across this question from USACO SILVER 2025, being new on cf took me hour(s) to crack it, and when I did, it used a basic property that SUM(abs(a[i]-x)) 1<=i<=n in an array a , is minimum if x is median. Sharing my approach and solution, Open for suggestions on how to improve thought process.

CODE->

#include <bits/stdc++.h>
using namespace std;

#define fastio() ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)

#define int long long
#define double long double

typedef long long ll;
typedef unsigned long long ull;

typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define endl '\n'

#define IN_VEC(v,n) vector<int> v(n); for(auto &i : v) cin >> i;
#define IN_ARR(arr,n) for(int i=0;i<n;i++) cin >> arr[i];

const ll INF = 1e18;
const int MOD = 1e9 + 7;
void solve() {
    int n,m;
    cin>>n>>m;
    vector<int> a(n),pref(2*n+1,0);
    for(int i=0;i<n;++i){
    	int y;
        cin>>y;
    	a[i]=y%m;
    }
    sort(all(a));
    for(int i=0;i<n;++i){
        a.pb(a[i]+m);
    }
    for(int i=1;i<=2*n;++i){
        pref[i]=pref[i-1]+a[i-1];
    }
    int ans=INF;
    for(int i=0;i<n;++i){
        // window from i to i+n-1 is sorted and shows unwraping of circle, its median minimizes cost 
        // each cut fixes x%m, there are n distinct cuts, so n distinct x%m that can minimize cost
        // make min cost over them
        // for a fixes cut this is just linear absolute sum --> min at median if sorted, which is!!
        int me=i+n/2;
        int t1=(me-i)*a[me];
        int t2=(pref[me]-pref[i]);
        int t3=(pref[n+i]-pref[me]);
        int t4=(n+i-me)*a[me];
        ans=min(ans,t1+t3-t2-t4);
    }
    cout<<ans<<endl;
}

int32_t main() {
    fastio();
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}