1798E - Multitest Generator - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
 
#define _ << ' ' <<
#define pb push_back
#define eb emplace_back
#define all(x) begin(x), end(x)
#define mp make_pair
#define f first
#define s second
#define sz(x) int((x).size())
#define each(x,A) for(auto &x: A)
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
 
using ll = long long;
using db = long double;
using pl = pair<ll,ll>;
using pi = pair<int,int>;
using cd = complex<db>;
using vi = vector<int>;
using vpi = vector<pi>;
using vd = vector<db>;
using vl = vector <ll>;
using str = string;
template<class T> using V = vector<T>; 
 
//const int MOD = 1e9+7;

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '('; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << ')'; }
template<typename T, size_t size> ostream& operator<<(ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; }

template<typename T > ostream& operator<<(ostream &os, const set<T> &st){os << '{'; string sep; for(const auto &x: st) os << sep << x, sep = ", "; return os << '}';}
template<typename A, typename B> ostream& operator<<(ostream &os, const map<A,B> &mm){os << '{'; string sep; for(const auto &x: mm) os << sep << x, sep = ", "; return os << '}';}

void solve(){
  int n;  cin >> n;
  vi a(n); each(x,a) cin >> x;
  vi pos(n,0);
  vi val(n,0);
  vi mx(n);
  int mxc = 0;
  for(int i=n-1; i>=0; i--){
    int v = a[i]+1;
    if(v+i==n){
      pos[i] = 1;
      mx[i] = mxc + 1;
    }
    if(v+i<n){
      if(pos[v+i]) pos[i] = pos[v+i]+1;
      mx[i] = max(mxc+1,1+mx[v+i]);
    }
    if(v+i>n){
      mx[i] = mxc+1;
    }
    mxc = max(mxc, pos[i]);
  }
  for(int i=0; i<n-1; i++){
    if(pos[i+1]==a[i]) cout << 0 << ' ';
    else if(mx[i+1]>=a[i] or pos[i+1]) cout << 1 << ' ';
    else cout << 2 << ' ';
  }
  cout << endl;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t;
  cin >> t;
  while(t--) solve();
}