#include<bits/stdc++.h>
#define taskname "A"
using namespace std;
template<class T>void minimize(T& a, T b){
if(a > b){
a = b;
}
}
template<class T>void maximize(T& a, T b){
if(a < b){
a = b;
}
}
const int lim = 5e5 + 5;
int n, t, a[lim];
namespace sub1{
void solve(){
int d = abs(a[1] % t - a[2] % t);
minimize(d, t - d);
cout << ((d + 1) >> 1);
}
}
namespace sub23{
void solve(){
if(t == 1){
return void(cout << 0);
}
for(int i = 2; i <= n; i++){
if((a[i] & 1) != (a[1] & 1)){
return void(cout << 1);
}
}
cout << 0;
}
}
namespace sub4{
void solve(){
int ans = t;
for(int i = 0; i < t; i++){
int candidate = 0;
for(int j = 1; j <= n; j++){
int d = abs(a[j] - i) % t;
maximize(candidate, min(d, t - d));
}
minimize(ans, candidate);
}
cout << ans;
}
}
namespace sub5{
struct Event{
int time, type, value;
Event(){}
Event(int _time, int _type, int _value) : time(_time), type(_type), value(_value) {}
bool operator <(const Event& other){
return this->time < other.time || (this->time == other.time && this->type > other.type);
}
};
void solve(){
vector<Event>event;
vector<multiset<int>>S(2);
for(int i = 1; i <= n; i++){
int mod = a[i] % t, p = (mod - (t >> 1) + t) % t;
event.emplace_back(p, 1, (t >> 1) + p);
if(p > mod){
event.emplace_back(0, 1, mod);
event.emplace_back(mod + 1, -1, mod);
}
else{
event.emplace_back(mod + 1, -1, (t >> 1) + p);
}
event.emplace_back(mod, 2, -mod);
if((p = (mod + (t >> 1)) % t) < mod){
event.emplace_back(0, 2, t - mod);
event.emplace_back(p + 1, -2, t - mod);
}
else{
event.emplace_back(p + 1, -2, -mod);
}
}
sort(event.begin(), event.end());
event.emplace_back(t, 0, 0);
int ans = t;
for(int i = 0; event[i].time < t; i++){
if(event[i].type > 0){
S[event[i].type - 1].insert(event[i].value);
}
else{
S[-event[i].type - 1].erase(S[-event[i].type - 1].find(event[i].value));
}
if(event[i].time != event[i + 1].time){
if(S[0].empty() && S[1].empty()){
minimize(ans, 0);
}
else if(S[0].empty()){
minimize(ans, max(0, *S[1].rbegin() + event[i].time));
}
else if(S[1].empty()){
minimize(ans, max(0, *S[0].rbegin() - event[i + 1].time + 1));
}
else{
int decrease = *S[0].rbegin() - event[i].time, increase = *S[1].rbegin() + event[i].time;
if(decrease > increase){
int opt_time = min(event[i + 1].time - 1, event[i].time + ((decrease - increase) >> 1));
minimize(ans, max(*S[0].rbegin() - opt_time, *S[1].rbegin() + opt_time));
}
else{
minimize(ans, increase);
}
}
minimize(ans, max(S[0].empty() ? 0 : *S[0].rbegin() - event[i].time, S[1].empty() ? 0 : *S[1].rbegin() + event[i].time));
}
}
cout << ans;
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if(fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
}
cin >> n >> t;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
if(n == 2){
sub1::solve();
}
else if(t <= 2){
sub23::solve();
}
else if(max(n, t) <= 3000){
sub4::solve();
}
else{
sub5::solve();
}
}
