#include "elephants.h"
#include <cmath>
#include <cstdio>
#include <unordered_map>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
int n,sqrt_n;
int arr[150005];
vector<iii> buckets[390]; //pair points to num used and the next uncovered one
unordered_map<int,int> elephants;
int num_buckets;
int cam;
int query_mod;
void comp(int i){
int cam_used=0;
int last=-1;
vector<iii>::reverse_iterator succ=buckets[i].rbegin();
for (vector<iii>::reverse_iterator it=buckets[i].rbegin();it!=buckets[i].rend();it++){
while ((*succ).first>(*it).first+cam){
cam_used=(*succ).second.first;
last=(*succ).second.second;
succ++;
}
if (cam_used){
(*it).second.first=cam_used+1;
(*it).second.second=last;
}
else{
(*it).second.first=1;
(*it).second.second=(*it).first+cam;
}
}
}
void print(){
for (int x=0;x<num_buckets;x++){
for (vector<iii>::iterator it=buckets[x].begin();it!=buckets[x].end();it++){
printf("%d %d %d %d\n",x,(*it).first,(*it).second.first,(*it).second.second);
}
}
printf("\n");
}
void rebalance(){
int pos[150005];
for (int x=0;x<n;x++){
pos[x]=arr[x];
}
sort(&pos[0],&pos[n]);
for (int x=0;x<=num_buckets;x++){
buckets[x].clear();
}
int iter=0;
int prev=-1;
for (int x=0;x<n;x++){
if ((int)buckets[iter].size()==sqrt_n){
iter++;
}
if (pos[x]!=prev){
buckets[iter].push_back(iii(pos[x],ii(0,0)));
prev=pos[x];
}
}
num_buckets=++iter;
buckets[num_buckets].push_back(iii(1000000005,ii(0,0)));
for (int x=0;x<num_buckets;x++) comp(x);
}
void init(int N, int l, int pos[]){
n=N;
for (int x=0;x<n;x++){
arr[x]=pos[x];
}
cam=l;
sqrt_n=sqrt(n);
for (int x=0;x<n;x++){
elephants[pos[x]]++;
}
rebalance();
}
int equals(int i, int j){ //find pos of element equal to j in bucket i
int a=0,b=buckets[i].size()-1,c;
while (a!=b){
c=(a+b)>>1;
if (buckets[i][c].first>j) b=c-1;
else if (buckets[i][c].first<j) a=c+1;
else return c;
}
return a;
}
int bigger(int i,int j){ //find pos of first element greater than j in bucket i
if (buckets[i].empty()) return 0;
int a=0,b=buckets[i].size()-1,c;
if (buckets[i][b].first<j) return b+1;
while (a!=b){
c=(a+b)>>1;
if (buckets[i][c].first<=j) a=c+1;
else if (c!=0 && buckets[i][c-1].first>j) b=c-1;
else return c;
}
return a;
}
int update(int i, int j){
if (elephants[arr[i]]==1){
for (int x=0;;x++){
if (!buckets[x].empty() && arr[i]<=(*buckets[x].rbegin()).first){
buckets[x].erase(buckets[x].begin()+equals(x,arr[i]));
comp(x);
break;
}
}
}
elephants[arr[i]]--;
arr[i]=j;
elephants[j]++;
if (elephants[j]==1){
for (int x=1;;x++){
if (!buckets[x].empty() && j<=(*buckets[x].begin()).first){
x--;
buckets[x].insert(buckets[x].begin()+bigger(x,j),iii(j,ii(0,0)));
comp(x);
break;
}
}
}
query_mod++;
if (query_mod==sqrt_n){
query_mod=0;
rebalance();
}
//print();
int ans=0;
int last=-1;
int succ;
for (int x=0;x<num_buckets;x++){
if (buckets[x].empty() || (*buckets[x].rbegin()).first<=last) continue;
succ=bigger(x,last);
ans+=buckets[x][succ].second.first;
last=buckets[x][succ].second.second;
}
return ans;
}
