We introduce an \(\mathrm{O}(N\log N)\) solution that finds the answer for each day independently, and an \(\mathrm{O}(N\log N)\) solution that finds the answer for a day based on that for the next day.

\(\mathrm{O}(N\log N)\) solution

For each \(i(1 \le i \le N)\), it is sufficient to find the minimum value greater than or equal to \(i\) in \((A_1,A_2,\dots,A_M)\).

First, prepare an array \(B\) where “\(B_i =\) how many times are fireworks launched in the first \(i\) days?” so that one can determine how many times the fireworks are launched between the \(l\)-th and \(r\)-th days in an \(\mathrm{O}(1)\) time by \(B_r - B_{l-1} \ge 1\).

Then, one can perform a binary search for each \(i\) to determine the minimum \(x\) such that fireworks are launched at least once between \(i\)-th and \(x\)-th days in an \(\mathrm{O}(\log N)\) time. This \(x\) corresponds to the day where fireworks are launched for the first time on or after the \(i\)-th day. Therefore, one can solve the problem for each \(i\) in an \(\mathrm{O}(N\log N)\) time.

Alternatively, one can directly find the answer with lower_bound.

\(\mathrm{O}(N)\) solution

First of all, the answer for the \(N\)-th day is \(0\) (since it is guaranteed that fireworks are launched on the \(N\)-th day.)

Here, let \(x\) be the answer for the \((i+1)\)-th day, and consider the answer for the \(i\)-th day. If the fireworks are launched on the \(i\)-th day, then the answer is \(0\); otherwise, the answer is \(x+1\).

Therefore, one can determine the answer as above for \(i=N-1,N-2,\dots,2,1\) in order to find the answer for all \(i\) in a total of \(\mathrm{O}(N)\) time.

Sample code (C++, \(\mathrm{O}(N\log N)\), using binary search)

#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,m;
  cin>>n>>m;
  vector<int> a(m);
  for(int i=0;i<m;i++){
    cin>>a[i];
    a[i]--;
  }
  vector<int> b(n+1);
  for(int i=0;i<m;i++) b[a[i]+1]++;
  for(int i=1;i<=n;i++) b[i]+=b[i-1];
  for(int i=0;i<n;i++){
    int ok=n,ng=i-1;
    while(abs(ok-ng)>1){
      int mid=(ok+ng)/2;
      if(b[mid+1]-b[i]>=1) ok=mid;
      else ng=mid;
    }
    cout<<ok-i<<endl;
  }
}

Sample code (C++, \(\mathrm{O}(N\log N)\), using lower_bound)

#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,m;
  cin>>n>>m;
  vector<int> a(m);
  for(int i=0;i<m;i++){
    cin>>a[i];
    a[i]--;
  }
  for(int i=0;i<n;i++){
    int x=*lower_bound(a.begin(),a.end(),i);
    cout<<x-i<<endl;
  }
}

Sample code (C++, \(\mathrm{O}(N)\) solution)

#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,m;
  cin>>n>>m;
  vector<int> a(m);
  for(int i=0;i<m;i++){
    cin>>a[i];
    a[i]--;
  }
  vector<int> b(n);
  for(int i=0;i<m;i++){
    b[a[i]]=1;
  }
  vector<int> ans(n);
  for(int i=n-1;i>=0;i--){
    if(b[i]){
      ans[i]=0;
    }
    else{
      ans[i]=ans[i+1]+1;
    }
  }
  for(int i=0;i<n;i++) cout<<ans[i]<<endl;
}