Traffic Lights

1#include<bits/stdc++.h>
2using namespace std;
3#define int long long
4signed main(){
5  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
6  int x,n; cin>>x>>n;
7  int a[n];
8  for(int i=0;i<n;++i) cin>>a[i];
9  map<int,bool> mp;
10  map<int,int> c;
11  mp[0]=1,mp[x]=1,c[x]=1;
12  for(int i=0;i<n;++i){
13    auto rg=mp.lower_bound(a[i]),lf=rg; --lf;
14    if(!--c[rg->first-lf->first]) c.erase(rg->first-lf->first);
15    ++c[rg->first-a[i]],++c[a[i]-lf->first];
16    mp[a[i]]=1;
17    cout<<c.rbegin()->first<<" ";
18  }
19  cout<<'\n';
20  return 0;
21}