//#include "elephants.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
//#define int long long
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 100000000000000000
#define bitebi __builtin_popcountll
#define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
#define YES cout <<"YES\n"
#define NO cout << "NO\n"
#define debug cout << "Here Fine" << endl ;
#define pr pair < int , int >
#define fbo find_by_order // returns iterator
#define ook order_of_key // returns strictly less numbers than key
using namespace std ;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
//using namespace __gnu_pbds;
//using namespace __gnu_cxx;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const double Pi=acos(-1.0);
const double EPS=1E-8;
const int mod = 1000000007 ;
const int mod1 = 998244353 ;
const int NN = 150001 ;
mt19937 R(time(0));
map < int , int > ma , ma1 ;
//int node[ 200 ][ 4 * NN ] ;
int n , l , block = 390 , w[ NN ] ;
vector < pair < int , int > > v[ 390 ] ;
pair < int , int > dp[ 400 ][ 900 ] ;
map < int , vector < int > > ps ;
void recalculate_dp( int i ){
FOR( j , 390 ) dp[ i ][ j ] = { 0 , 0 } ;
if( v[ i ].size() == 0 ) return ;
int lst = v[ i ].size() ;
for( int j = v[ i ].size() - 1 ; j >= 0 ; j -- ){
int nx = v[ i ][ j ].f + l ;
while( true ){
if( v[ i ][ lst - 1 ].f > nx ) lst -- ;
else break ;
}
if( lst == v[ i ].size() ){
dp[ i ][ j ] = { 1 , nx } ;
}
else{
dp[ i ][ j ].f = 1 + dp[ i ][ lst ].f ;
dp[ i ][ j ].s = dp[ i ][ lst ].s ;
}
}
}
void gadaamushave(){
vector < int > vu ;
FOR( i , 390 ){
for( auto x : v[ i ] ) vu.pb( x.f ) ;
v[ i ].clear() ;
}
int cnt = 0 , pos = 0 ;
ps.clear() ;
FOR( i , n ){
if( cnt == block ){
cnt = 0 ; pos ++ ;
}
cnt ++ ;
ps[ vu[ i ] ].pb( pos ) ;
int ss = v[ pos ].size() ;
v[ pos ].pb( { vu[ i ] , ss } ) ;
}
FOR( i , 390 ){
recalculate_dp( i ) ;
}
}
void init(int N, int L, int X[]){
n = N , l = L ;
FOR( i , N ) w[ i ] = X[ i ] ;
int cnt = 0 , pos = 0 ;
FOR( i , N ){
if( cnt == block ){
cnt = 0 ; pos ++ ;
}
cnt ++ ;
int ss = v[ pos ].size() ;
v[ pos ].pb( { X[ i ] , ss } ) ;
}
gadaamushave() ;
}
int cc = 0 ;
int daitrie_pasuxi(){
int ans = 0 ;
int lst = -1 ;
pair < int , int > p ;
FOR( i , 390 ){
if( v[ i ].size() == 0 ) continue ;
p = { lst , INT_MAX } ;
if( v[ i ][ v[ i ].size() - 1 ].f <= lst ){
continue ;
}
p = *upper_bound( v[ i ].begin() , v[ i ].end() , p ) ;
ans = ans + dp[ i ][ p.s ].f ;
lst = dp[ i ][ p.s ].s ;
}
return ans ;
}
int update(int i , int y){
if( n == 1 ) return 1 ;
cc ++ ;
int ss = ps[ w[ i ] ].size() - 1 ;
int pos = ps[ w[ i ] ][ ss ] , ww = w[ i ] ;
ps[ w[ i ] ].pop_back() ;
w[ i ] = y ;
// ar dagaviwydes ps is ganaxleba
int tt = 0 ;
FOR( i , v[ pos ].size() ){
if( tt == 1 ){
v[ pos ][ i ].s -- ;
continue ;
}
if( v[ pos ][ i ].f == ww ){
v[ pos ].erase( v[ pos ].begin() + i ) ;
i -- ;
tt = 1 ;
continue ;
}
}
recalculate_dp( pos ) ;
// axla ipove sad chaagdo
int lst = 0 ; pos = -1 ;
FOR( i , 390 ){
if( v[ i ].size() == 0 ) continue ;
lst = i ;
ss = v[ i ].size() - 1 ;
if( v[ i ][ ss ].f >= y ){
pos = i ; break ;
}
}
if( pos == -1 ) pos = lst ;
ps[ w[ i ] ].pb( pos ) ;
ss = v[ pos ].size() ;
v[ pos ].pb( { w[ i ] , ss } ) ;
for( int j = v[ pos ].size() - 1 ; j > 0 ; j -- ){
if( v[ pos ][ j - 1 ].f <= v[ pos ][ j ].f ) break ;
v[ pos ][ j - 1 ].s ++ ;
v[ pos ][ j ].s -- ;
swap( v[ pos ][ j - 1 ] , v[ pos ][ j ] ) ;
}
recalculate_dp( pos ) ;
int ans = daitrie_pasuxi() ;
if( cc == block){
cc = 0 ;
gadaamushave() ;
}
return ans ;
}
//#define MAX_N 1000000
//#define MAX_M 1000000
//
//static int N,L,M;
//static int X[MAX_N];
//static int ii[MAX_M];
//static int yy[MAX_M];
//
//void read_input()
//{
// int i;
// scanf("%d %d %d",&N,&L,&M);
// for(i=0; i<N; i++)
// scanf("%d",&X[i]);
// for(i=0; i<M; i++)
// scanf("%d %d",&ii[i],&yy[i]);
//}
//
//int main()
//{
// int i, ans;
//
// read_input();
// init(N,L,X);
// for(i=0; i<M; i++) {
// ans = update(ii[i],yy[i]);
// printf("%d\n", ans);
// }
// return 0;
//}
