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 vi; typedef vector 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 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 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; }