Every light switch in position i can turn on at most one switch located in i+Ai th position. And a switch can be turned on manually or by one or more switches from its left.

So we can calculate and store the number of switches that can turn on any switch in any position i in a map/array named count[]. and if there are no such switch that can turn on the switch at any position i then the i th switch must be turned on manually.

Before jumping into the query we will calculate the total number of switches 'X' that needs to be turn on manually or in other words the total number of i where count[i] == 0;

then in the i th query :

if the i th switch is half-defected then it will only put an effect in the i+Ai th switch. Replacing Ai=0 will decrease count[i+A[i]] by one. if initially count[i+A[i]]==1 then replacing Ai = 0 , count[i+Ai] will be 0. in this case we have to turn on one more switch (in i+ai th index) manually. so the answer of the quary will be X+1, in all other case the answer will be X

time complexity : O(N)

code:

/*

• Copyright (c) 2024 Emon Thakur
• All rights reserved.
  */
  #include<bits/stdc++.h>
  using namespace std;
  void solve()
  {
  int n; cin>>n;
  int a[n];
  for(int i=0;i<n;i++) cin>>a[i];
  int count[n]={0};
  int ans=0;
  for(int i=0;i<n;i++)
  {
  if(count[i]==0) ans++;
  if(i+a[i] < n) count[i+a[i]]++;
  }

for(int i=0;i<n;i++)
{
    if(i+a[i]<n && count[i+a[i]]==1) cout<<ans+1<<" ";
    else cout<<ans<<" ";
}
cout<<endl;

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