#include "elephants.h"
#include <math.h>

#define MAXN 150004
#define MAXS 390

static int L,G,SZ,update_count;
static int X[MAXN],P[MAXN];

static struct GROUP{
    int arr[MAXS*2],count[MAXS*2],last[MAXS*2],size;
    void set(){
        int i,k=size;
        for (i=size;i;i--){
            while (k > i && arr[k-1]-arr[i] > L) k--;
            if (arr[size]-arr[i] <= L) count[i] = 1, last[i] = arr[i]+L;
            else count[i] = count[k]+1, last[i] = last[k];
        }
    }
} groups[MAXS];

void all_set()
{
    int N=0,i,j;
    for (i=1;i<=G;i++){
        for (j=1;j<=groups[i].size;j++) X[++N] = groups[i].arr[j];
        groups[i].size = 0;
    }
    G = 1;
    for (i=1;i<=N;i++){
        if (groups[G].size == SZ) G++;
        groups[G].arr[++groups[G].size] = X[i];
    }
    for (i=1;i<=G;i++) groups[i].set();
    update_count = 0;
}

int get_answer()
{
    int i,ans=groups[1].count[1],last=groups[1].last[1];
    int s,e,m,t;
    for (i=2;i<=G;i++){
        if (groups[i].arr[groups[i].size] <= last) continue;
        s = 1, e = groups[i].size;
        while (s <= e){
            m = (s+e)>>1;
            if (groups[i].arr[m] > last) e = m-1, t = m;
            else s = m+1;
        }
        ans += groups[i].count[t];
        last = groups[i].last[t];
    }
    return ans;
}

int del(int p)
{
    int i,t;
    for (t=1;t<G;t++) if (groups[t].arr[1] <= p && groups[t+1].arr[1] > p) break;
    for (i=1;i<=groups[t].size;i++){
        if (groups[t].arr[i] == p){
            for (;i<groups[t].size;i++) groups[t].arr[i] = groups[t].arr[i+1];
            groups[t].size--;
            break;
        }
    }
    groups[t].set();
    return groups[t].size;
}

void add(int p)
{
    int i,t,x;
    for (t=1;t<G;t++) if (groups[t].arr[groups[t].size] > p) break;
    for (x=1;x<=groups[t].size;x++) if (groups[t].arr[x] > p) break;
    for (i=groups[t].size;i>=x;i--) groups[t].arr[i+1] = groups[t].arr[i];
    groups[t].arr[x] = p;
    groups[t].size++;
    groups[t].set();
}

void init(int N, int l, int x[])
{
    int i;
    L = l;
    SZ = (int)sqrt((double)N); G = 1;
    for (i=0;i<N;i++){
        P[i] = x[i];
        if (groups[G].size == SZ) G++; /* TODO: modify */
        groups[G].arr[++groups[G].size] = x[i];
    }
    for (i=1;i<=G;i++) groups[i].set();
}

int update(int i, int y)
{
    if (++update_count == SZ) all_set();
    if (!del(P[i])) all_set();
    add(P[i]=y);
    return get_answer();
}