#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define perl(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define pb push_back
#define ins insert
#define all(x) (x).begin(),(x).end()
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[8]={1,0,-1,0,1,1,-1,-1};
const ll dx[8]={0,-1,0,1,1,-1,1,-1};
using Graph = vector<vector<int>>;
const ll mod=1000000007;
const int MAX_N = 1000;         // n の最大値
 
double nCk(int n, int k) {
double res=1.0;
for(int i=0; i<n; i++){
res*=0.5;}
for(int i=0; i<k; i++){
res*=(double)(n-i);
res/=(double)(k-i);
}
return res;}
 
int main() {
ll n,p;
cin>>n>>p;
ll ca=0;
ll a[n+2]={};
ll b[n+2]={};
ll m=0;
ll f=0;
for(ll i=1; i<n+1; i++){
cin>>a[i];}
for(ll i=0; i<p; i++){
  
for(ll k=1; k<=n; k++){
if(k-a[k]<=0){
b[0]++;}
else{
b[k-a[k]]++;}
if(k+a[k]>=n){
b[n+1]--;}
else{
b[k+a[k]+1]--;}}
ca=b[0];
b[0]=0;
for(ll k=1; k<=n; k++){
ca+=b[k];
b[k]=0;
a[k]=ca;
if(a[k]==n){
m++;}
}
if(m==n) {f++; break;}
m=0;
ca=0;}
for(ll i=1; i<=n; i++){
cout << a[i] << " ";}
cout << endl;}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const long long INF = 1e15;

struct BIT {
  int n;
  vector<long long> d;
  BIT(int n=0):n(n),d(n+1) {}
  void add(int i, long long x=1) {
    for (i++; i <= n; i += i&-i) {
      d[i] += x;
    }
  }
  long long sum(int i) {
    long long x = 0;
    for (i++; i; i -= i&-i) {
      x += d[i];
    }
    return x;
  }
  long long sum(int l, int r) {
    return sum(r-1) - sum(l-1);
  }
};

int main(){
    int n,q;
    cin >> n >> q;
    vector<int> c(n);
    for(int i = 0; i < n; i++) cin >> c[i], c[i]--;

    vector<pair<pair<int,int>,int>> pq;
    for(int i = 0; i < q; i++){
        int l,r;
        cin >> l >> r;
        l--;r--;
        pq.push_back(make_pair(make_pair(l,r),i));
    }

    vector<int> memo(n,-1);
    vector<pair<int,int>> cp;
    for(int i = 0; i < n; i++){
        if(memo[c[i]] != -1) cp.push_back(make_pair(memo[c[i]],i));
        memo[c[i]] = i;
    }

    sort(pq.rbegin(),pq.rend());
    sort(cp.rbegin(),cp.rend());

    BIT tree(n);
    vector<int> ans(q,0);

    int ncp = 0;
    for(int i = 0; i < q; i++){
        while(true){
            if(ncp < (int)cp.size() && pq[i].first.first <= cp[ncp].first){
                tree.add(cp[ncp].second,1);
                ncp++;
            } else break;
        }
        ans[pq[i].second] = pq[i].first.second-pq[i].first.first+1-tree.sum(pq[i].first.second);
    }

    for(int i = 0; i < q; i++) cout << ans[i] << endl;


    return 0;
}