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();
}