#include <bits/stdc++.h> using namespace std; #define int long long #define fi first #define se second #define sz(x) ((int)x.size()) #define all(a) (a).begin(), (a).end() #define inpvi(a, n) vi a(n); for(auto &i : a) cin >> i; int iceil(int a, int b) { return (a+b-1)/b; } multiset<int> l, r; int suml = 0, sumr = 0; void ins(int x) { if(l.empty() || *l.rbegin() >= x) { l.insert(x); suml += x; if(sz(l) > sz(r) + 1) { int y = *l.rbegin(); l.erase(l.find(y)); suml -= y; r.insert(y); sumr += y; } } else { r.insert(x); sumr += x; if(sz(r) > sz(l)) { int y = *r.begin(); r.erase(r.begin()); sumr -= y; l.insert(y); suml += y; } } } void del(int x) { if(*l.rbegin() >= x) { l.erase(l.find(x)); suml -= x; if(sz(r) > sz(l)) { int y = *r.begin(); r.erase(r.begin()); sumr -= y; l.insert(y); suml += y; } } else { r.erase(r.find(x)); sumr += x; if(sz(l) > sz(r) + 1) { int y = *l.rbegin(); l.erase(l.find(y)); suml -= y; r.insert(y); sumr += y; } } } int res() { return iceil(*r.rbegin() - *l.begin(), 2); } bool chmin(int &a, int b) { bool r = a > b; a = min(a,b); return r; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); /* ins(1); ins(2); ins(4); ins(3); for(int i : l) cout << i << ' '; cout << '\n'; for(int i : r) cout << i << ' '; cout << '\n'; */ int n,t; cin >> n >> t; vector<pair<int, bool>> a(n); for(int i = 0; i < n; ++i) { cin >> a[i].fi; a[i].se = (a[i].fi >= t); a[i].fi %= t; //cerr << a[i].fi << ' '; } sort(all(a)); for(int i = 0; i < n; ++i) ins(a[i].fi); int ans = res(); for(int i = 0; i < n; ++i) { int x = a[i].fi; if(a[i].se) { del(x); ins(x+t); } /* for(int i : l) cerr << i << ' '; cerr << '\n'; for(int i : r) cerr << i << ' '; cerr << '\n'; */ chmin(ans, res()); } cout << ans; }