Link to this code: https://cses.fi/paste/6dd8197e09444dee15e52e/
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define int ll // delete if causing problems
#define ld long double
#define pb push_back
#define pf push_front
#define mp make_pair
#define fir first
#define sec second
#define all(a) a.begin(), a.end()
#define fast_io ios_base::sync_with_stdio(false); cin.tie(0);

const int maxn = 200010;
const int MOD = 1e9+7;
const int MOD2 = 998244353;
const int INF = 1e9;
const ll LINF = 1e18;
int n, m, a[maxn], b[maxn];
map<int, int> M, N;
string s, ss;
set<int> S;

void solve()
{
    int x, n;
    cin >> x >> n;
    set<pair<int,int>> S;
    S.insert({0,x});
    int ans = x;
    for(int i = 0; i < n; i++)
    {
        int y; cin >> y;
        auto it = S.lower_bound({y, x}); // nearest point >= y
        auto it2 = (--it); it++; // previous point before nearest point >= y
        auto Q = *(it2);
        int A = Q.fir, B = Q.sec;
        Q = *(it2);
        int X = Q.fir, Y = Q.sec;
        if(X>y)swap(A, X), swap(B, Y); // Go to previous point instead
        S.erase({A,B}); // remove the big point
        S.insert({A,y}); // create two smaller points A - y
        S.insert({y,B}); // and y - B
        if(y-A<B-y)
        {
            //check if new maximum for B-y
        }
        else
        {
            //check if new maximum for A-y
        }
        cout << ans << " ";
    }
}

int32_t main()
{
    fast_io;
    int t=1; //cin >> t;
    while(t--) solve();
}