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

struct RozsiewaczChaosu {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t ziarno = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + ziarno);
    }
};

struct MalaPierwszaBeczka {
    int krok;
    int przesuniecie;
    int najlepszy_wynik;
    unordered_map<int, int, RozsiewaczChaosu> ile_reszt_ma_taki_wynik;
};

static const int granica_malych = 5000;
static const int granica_duzych_wynikow = 2000;
static const int prog_ignorowania_duzych = 2 * granica_duzych_wynikow;
static const int prog_wyrzucania_duzych = 6000;

int liczba_pol, liczba_operacji;
vector<int> wielki_bigos_duzych;
vector<int> gdzie_siedzi_kamien;
vector<int> zywe_kamienie;
vector<MalaPierwszaBeczka> male_beczki;
vector<int> liczby_resztowe_w_jednym_wiadrze;
vector<int> ile_malych_ma_taki_globalny_wynik;
int najlepszy_maly = 0;

unordered_map<uint64_t, int, RozsiewaczChaosu> wielki_rejestr_duzych;
vector<int> ile_duzych_klas_ma_rozmiar;
int najlepszy_duzy = 0;
bool czy_duze_sa_zbudowane = false;

vector<uint64_t> tymczasowa_lyzka;

vector<int> zrob_sito_i_prymy(int limit) {
    vector<bool> sito(limit + 1, false);
    vector<int> prymy;
    for (int i = 2; i <= limit; ++i) {
        if (!sito[i]) {
            prymy.push_back(i);
            if (1LL * i * i <= limit) {
                for (int j = i * i; j <= limit; j += i) sito[j] = true;
            }
        }
    }
    return prymy;
}

void przygotuj_male_prymy() {
    vector<int> prymy = zrob_sito_i_prymy(granica_malych);

    long long suma_rozmiarow = 0;
    for (int p : prymy) suma_rozmiarow += p;
    liczby_resztowe_w_jednym_wiadrze.assign((int)suma_rozmiarow, 0);

    male_beczki.reserve(prymy.size());
    ile_malych_ma_taki_globalny_wynik.assign(liczba_operacji + 5, 0);

    int przes = 0;
    for (int p : prymy) {
        MalaPierwszaBeczka beczka;
        beczka.krok = p;
        beczka.przesuniecie = przes;
        beczka.najlepszy_wynik = 0;
        beczka.ile_reszt_ma_taki_wynik.reserve(8);
        beczka.ile_reszt_ma_taki_wynik[0] = p;
        male_beczki.push_back(move(beczka));
        przes += p;
    }

    ile_malych_ma_taki_globalny_wynik[0] = (int)male_beczki.size();
    najlepszy_maly = 0;
}

void przygotuj_duze_prymy() {
    wielki_bigos_duzych.assign(liczba_pol + 1, 0);
    vector<int> wszystkie_prymy = zrob_sito_i_prymy(liczba_pol);
    for (int p : wszystkie_prymy) {
        if (p <= granica_malych) continue;
        for (int wielokrotny = p; wielokrotny <= liczba_pol; wielokrotny += p) {
            wielki_bigos_duzych[wielokrotny] = p;
        }
    }
}

inline void popraw_male_beczki(int pole, int zmiana) {
    for (auto &beczka : male_beczki) {
        int stary_naj = beczka.najlepszy_wynik;
        int reszta = pole % beczka.krok;
        int gdzie = beczka.przesuniecie + reszta;
        int stary = liczby_resztowe_w_jednym_wiadrze[gdzie];
        int nowy = stary + zmiana;
        liczby_resztowe_w_jednym_wiadrze[gdzie] = nowy;

        auto it_stary = beczka.ile_reszt_ma_taki_wynik.find(stary);
        --it_stary->second;
        if (it_stary->second == 0) beczka.ile_reszt_ma_taki_wynik.erase(it_stary);

        ++beczka.ile_reszt_ma_taki_wynik[nowy];

        if (nowy > beczka.najlepszy_wynik) {
            beczka.najlepszy_wynik = nowy;
        } else if (stary_naj == stary) {
            auto it_naj = beczka.ile_reszt_ma_taki_wynik.find(stary_naj);
            if (it_naj == beczka.ile_reszt_ma_taki_wynik.end()) {
                --beczka.najlepszy_wynik;
            }
        }

        int nowy_naj = beczka.najlepszy_wynik;
        if (stary_naj != nowy_naj) {
            --ile_malych_ma_taki_globalny_wynik[stary_naj];
            ++ile_malych_ma_taki_globalny_wynik[nowy_naj];
        }
    }

    while (najlepszy_maly > 0 && ile_malych_ma_taki_globalny_wynik[najlepszy_maly] == 0) --najlepszy_maly;
    while (najlepszy_maly + 1 < (int)ile_malych_ma_taki_globalny_wynik.size() && ile_malych_ma_taki_globalny_wynik[najlepszy_maly + 1] > 0) ++najlepszy_maly;
}

inline uint64_t ulepic_klucz(int prym, int reszta) {
    return (uint64_t(prym) << 32) ^ uint32_t(reszta);
}

void dorzuc_do_duzych(int pole) {
    tymczasowa_lyzka.clear();
    for (int inny : zywe_kamienie) {
        int roznica = abs(pole - inny);
        if (roznica == 0) continue;
        int duzy_prym = wielki_bigos_duzych[roznica];
        if (duzy_prym > granica_malych) {
            tymczasowa_lyzka.push_back(ulepic_klucz(duzy_prym, pole % duzy_prym));
        }
    }
    if (tymczasowa_lyzka.empty()) return;

    sort(tymczasowa_lyzka.begin(), tymczasowa_lyzka.end());

    for (int i = 0; i < (int)tymczasowa_lyzka.size();) {
        int j = i + 1;
        while (j < (int)tymczasowa_lyzka.size() && tymczasowa_lyzka[j] == tymczasowa_lyzka[i]) ++j;

        uint64_t klucz = tymczasowa_lyzka[i];
        auto it = wielki_rejestr_duzych.find(klucz);
        if (it == wielki_rejestr_duzych.end()) {
            wielki_rejestr_duzych[klucz] = 2;
            ++ile_duzych_klas_ma_rozmiar[2];
            najlepszy_duzy = max(najlepszy_duzy, 2);
        } else {
            int stary = it->second;
            --ile_duzych_klas_ma_rozmiar[stary];
            ++it->second;
            ++ile_duzych_klas_ma_rozmiar[stary + 1];
            najlepszy_duzy = max(najlepszy_duzy, stary + 1);
        }

        i = j;
    }
}

void zabierz_z_duzych(int pole) {
    tymczasowa_lyzka.clear();
    for (int inny : zywe_kamienie) {
        if (inny == pole) continue;
        int roznica = abs(pole - inny);
        int duzy_prym = wielki_bigos_duzych[roznica];
        if (duzy_prym > granica_malych) {
            tymczasowa_lyzka.push_back(ulepic_klucz(duzy_prym, pole % duzy_prym));
        }
    }
    if (tymczasowa_lyzka.empty()) return;

    sort(tymczasowa_lyzka.begin(), tymczasowa_lyzka.end());

    for (int i = 0; i < (int)tymczasowa_lyzka.size();) {
        int j = i + 1;
        while (j < (int)tymczasowa_lyzka.size() && tymczasowa_lyzka[j] == tymczasowa_lyzka[i]) ++j;

        uint64_t klucz = tymczasowa_lyzka[i];
        auto it = wielki_rejestr_duzych.find(klucz);
        int stary = it->second;
        --ile_duzych_klas_ma_rozmiar[stary];
        if (stary == 2) {
            wielki_rejestr_duzych.erase(it);
        } else {
            it->second = stary - 1;
            ++ile_duzych_klas_ma_rozmiar[stary - 1];
        }

        i = j;
    }

    while (najlepszy_duzy > 1 && ile_duzych_klas_ma_rozmiar[najlepszy_duzy] == 0) --najlepszy_duzy;
}

void odbuduj_duze_od_zera() {
    wielki_rejestr_duzych.clear();
    ile_duzych_klas_ma_rozmiar.assign(prog_wyrzucania_duzych + 5, 0);
    najlepszy_duzy = 1;
    czy_duze_sa_zbudowane = true;

    vector<int> stare_zywe = zywe_kamienie;
    vector<int> puste;
    puste.reserve(stare_zywe.size());
    zywe_kamienie.clear();
    for (int x : stare_zywe) {
        dorzuc_do_duzych(x);
        zywe_kamienie.push_back(x);
    }
}

void wylacz_duze() {
    wielki_rejestr_duzych.clear();
    ile_duzych_klas_ma_rozmiar.clear();
    najlepszy_duzy = 0;
    czy_duze_sa_zbudowane = false;
}

inline void dorzuc_kamien(int pole) {
    if (czy_duze_sa_zbudowane) dorzuc_do_duzych(pole);
    gdzie_siedzi_kamien[pole] = (int)zywe_kamienie.size();
    zywe_kamienie.push_back(pole);
    popraw_male_beczki(pole, +1);

    if (czy_duze_sa_zbudowane && (int)zywe_kamienie.size() > prog_wyrzucania_duzych) {
        wylacz_duze();
    }
}

inline void zabierz_kamien(int pole) {
    if (czy_duze_sa_zbudowane) zabierz_z_duzych(pole);
    popraw_male_beczki(pole, -1);

    int idx = gdzie_siedzi_kamien[pole];
    int ostatni = zywe_kamienie.back();
    swap(zywe_kamienie[idx], zywe_kamienie.back());
    gdzie_siedzi_kamien[ostatni] = idx;
    zywe_kamienie.pop_back();
    gdzie_siedzi_kamien[pole] = -1;

    if (!czy_duze_sa_zbudowane && (int)zywe_kamienie.size() <= prog_ignorowania_duzych) {
        odbuduj_duze_od_zera();
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> liczba_pol >> liczba_operacji;

    gdzie_siedzi_kamien.assign(liczba_pol + 1, -1);
    zywe_kamienie.reserve(liczba_operacji);
    tymczasowa_lyzka.reserve(prog_wyrzucania_duzych + 5);

    przygotuj_male_prymy();
    przygotuj_duze_prymy();

    for (int i = 0; i < liczba_operacji; ++i) {
        int pole;
        cin >> pole;

        if (gdzie_siedzi_kamien[pole] == -1) dorzuc_kamien(pole);
        else zabierz_kamien(pole);

        int wynik = najlepszy_maly;
        if (czy_duze_sa_zbudowane) wynik = max(wynik, najlepszy_duzy);
        cout << wynik << '\n';
    }

    return 0;
}