#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "grader.h"
#define int long long
struct BST {
struct Node {
int key;
int cnt = 1;
int sum = key;
int min_key = key;
int max_key = key;
int size = 1;
int height = 1;
Node* left = nullptr;
Node* right = nullptr;
static int get_sum(Node* node) {
if (node == nullptr) {
return 0;
}
return node->sum;
}
static int get_min_key(Node* node) {
if (node == nullptr) {
return INT_MAX;
}
return node->min_key;
}
static int get_max_key(Node* node) {
if (node == nullptr) {
return INT_MIN;
}
return node->max_key;
}
static int get_size(Node* node) {
if (node == nullptr) {
return 0;
}
return node->size;
}
static int get_height(Node* node) {
if (node == nullptr) {
return 0;
}
return node->height;
}
static void update(Node* node) {
node->sum = node->key * node->cnt + get_sum(node->left) + get_sum(node->right);
node->min_key = min(node->key, min(get_min_key(node->left), get_min_key(node->right)));
node->max_key = max(node->key, max(get_max_key(node->left), get_max_key(node->right)));
node->size = node->cnt + get_size(node->left) + get_size(node->right);
node->height = 1 + max(get_height(node->left), get_height(node->right));
}
static void rotate_left(Node*& node) {
Node* temp = node->right;
node->right = temp->left;
temp->left = node;
node = temp;
}
static void rotate_right(Node*& node) {
Node* temp = node->left;
node->left = temp->right;
temp->right = node;
node = temp;
}
static bool insert(Node*& node, int key) {
if (node == nullptr) {
node = new Node{key};
return true;
}
bool inserted;
if (key < node->key) {
inserted = insert(node->left, key);
}
else if (key > node->key) {
inserted = insert(node->right, key);
}
else {
inserted = false;
node->cnt++;
node->sum+=node->key;
}
if (inserted) {
int hl = get_height(node->left);
int hr = get_height(node->right);
if (hr - hl > 1) {
rotate_left(node);
update(node->left);
}
else if (hl - hr > 1) {
rotate_right(node);
update(node->right);
}
update(node);
}
return inserted;
}
static pair<int,int> range_query(Node* node, int l, int h) {
if (node == nullptr) {
return {0,0};
}
if (node->max_key < l || node->min_key > h) {
return {0,0};
}
if (node->min_key >= l && node->max_key <= h) {
return {node->sum,node->size};
}
auto a=range_query(node->left, l, h);
auto b=range_query(node->right, l, h);
a.first+=b.first;
a.second+=b.second;
if (node->key >= l && node->key <= h) {
a.first+=node->key * node->cnt;
a.second+=node->cnt;
}
return a;
}
};
Node* root = nullptr;
bool insert(int key) {
return Node::insert(root, key);
}
pair<int,int>range_query(int min_key, int max_key) {
return Node::range_query(root, min_key, max_key);
}
};
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N=getN(),K=getK(),M=4e8;
// if(N>1000)return 1;
ordered_set<int>s;
BST t;
auto calc=[&](int x)->int{
// int cc=0;
// for(int i:s){
// if(i<x){
// cc+=x-i;
// }
// if(i>x+K){
// cc+=i-(x+K);
// }
// }
int c=0;
auto aa=t.range_query(0,x);
auto bb=t.range_query(x+K,M);
c+=-aa.first+x*aa.second;
c+=bb.first-(x+K)*bb.second;
// if(c!=cc)exit(1);
return c;
};
for(int i=0;i<N;i++){
int y=Data();
s.insert(y);
t.insert(y);
int ans=1e18;
{
int l=0,h=i;
while(l<h){
int m=(l+h)/2;
if(m>=i-s.order_of_key(*s.find_by_order(m)+K)){
h=m;
}
else{
l=m+1;
}
}
if(h>0)ans=min(ans,calc(*s.find_by_order(h-1)));
else ans=min(ans,calc(*s.find_by_order(h)));
}
{
int l=0,h=i;
while(l<h){
int m=(l+h)/2;
if(s.order_of_key(*s.find_by_order(m)-K)>=i-m){
h=m;
}
else{
l=m+1;
}
}
if(h>0)ans=min(ans,calc(*s.find_by_order(h-1)-K));
ans=min(ans,calc(*s.find_by_order(h)-K));
}
Solution(ans);
}
return 0;
}