#include <stdio.h>
#include <stdlib.h>
#define MAX_K  100

struct node {
  int value;
  int min,max,delta;
  struct node *left,*right,*parent;
  int left_c,right_c;
};

struct node *root=NULL;  //kořen stromu
int hodnoty[MAX_K]; //posledních $K$ načtených hodnot
int N,K;

void bbtree_oprav(struct node *); //nadeklarujeme až později

struct node *bbtree_find(struct node *ptr,int value) {
  if (value < ptr->value && ptr->left) return bbtree_find(ptr->left,value);
  if (value > ptr->value && ptr->right) return bbtree_find(ptr->right,value);
  return ptr;
}

void bbtree_insert(int value) { //vloží vrchol do stromu
  struct node *new=malloc(sizeof(struct node)),*ptr;
  new->value=new->min=new->max=value;
  new->left=new->right=new->parent=NULL;
  new->delta=new->left_c=new->right_c=0;
  
  if (!root) root=new; //ještě nemám root
  else {
    ptr=bbtree_find(root,value);

    new->parent=ptr;  //napojíme na rodiče
    if (value < ptr->value) ptr->left=new; else ptr->right=new; //a rodiče na mě
    bbtree_oprav(new);
  }
}

void bbtree_remove(int value) { //odebere vrchol
  struct node *ptr=bbtree_find(root,value),*son;

  if (!ptr || ptr->value != value) return; //nenašli jsme -- to se nám nestane
  if (ptr->left && ptr->right) { //mám oba syny -- najdi za sebe náhradu
    struct node *nahrada=(ptr->left_c>ptr->right_c) ? ptr->left : ptr->right;
    while ((ptr->left_c>ptr->right_c) ? nahrada->right : nahrada->left)
      nahrada=(ptr->left_c>ptr->right_c) ? nahrada->right : nahrada->left;
    ptr->value=nahrada->value;
    ptr=nahrada;
  }

  son=(ptr->left) ? ptr->left : ptr->right;  
  if (son) son->parent=ptr->parent; // úprava syna
  if (!ptr->parent) root=son; //úprava rodiče
  else if (ptr->parent->left==ptr) ptr->parent->left=son; else ptr->parent->right=son;

  if (ptr->parent) bbtree_oprav(ptr->parent);
  free(ptr);
}

void bbtree_update_vrcholu(struct node *ptr) {  //přepočítá {\it min, max, delta, left_c} a {\it right_c}
#define test_delta(a) if ((a) && (ptr->delta==-1 || (a) < ptr->delta)) ptr->delta=(a); 
  ptr->min=(ptr->left) ? ptr->left->min : ptr->value;
  ptr->max=(ptr->right) ? ptr->right->max : ptr->value;
  ptr->delta=-1; //delta neinicializovaná
  if (ptr->left) { //pomůže mi levý syn?
    test_delta(ptr->left->delta);
    test_delta(ptr->value - ptr->left->max);
  }
  if (ptr->right) {//a co pravý syn?
    test_delta(ptr->right->delta);
    test_delta(ptr->right->min - ptr->value);
  }
  if (ptr->delta<0) ptr->delta=0;
  ptr->left_c=(ptr->left) ? ptr->left->left_c + 1 + ptr->left->right_c: 0;
  ptr->right_c=(ptr->right) ? ptr->right->left_c + 1 + ptr->right->right_c: 0;
}

 //tohle vytvoří spoják z vrcholů v stromu s vrcholem ptr a vrátí to první prvek p
 //spoják je svázaný --$>$left pointerama, jenom p--$>$right je {\it konec} spojáčku
 //a p--$>$right_c je {\it počet} prvků ve spojáčku
struct node *bbtree_collect(struct node *ptr) {
  struct node *begin;
  if (ptr->left) {  //někdo vlevo?
    begin=bbtree_collect(ptr->left);
    begin->left->right=ptr;
  } else {begin=ptr;begin->right_c=0;}
  begin->left=ptr;
  begin->right_c++;
  if (ptr->right) {//a co vpravo?
    begin->left->right=bbtree_collect(ptr->right);
    begin->right_c+=begin->left->right->right_c;
    begin->left=begin->left->right->left;
  }
  return begin;
}

 //tohle z výše popsaného spojáčku udělá vyvážený strom
 //parametr next ukazuje na první dosud nepoužitý prvek z popsaného seznamu
struct node *bbtree_rebuild(struct node *spojak,struct node **next) {
  int l=spojak->right_c/2;  //počet vrcholů vlevo
  int r=spojak->right_c-l-1;//a vpravo
  struct node *left=NULL,*right=NULL;

  if (l) {spojak->right_c=l;left=bbtree_rebuild(spojak,next);spojak=*next;}
  *next=spojak->right; //toto je momentálně první nepoužitý prvek
  if (r) {spojak->right->right_c=r;right=bbtree_rebuild(spojak->right,next);}

  spojak->left=left;  //spoják bude kořen
  if (left) left->parent=spojak; //upravit pointery na syny a rodiče
  spojak->right=right;
  if (right) right->parent=spojak;
  bbtree_update_vrcholu(spojak);
  return spojak;
}

 //tato funkce se stará o opravu hodnot {\it min,max} a {\it delta} ve stromě
 //podle potřeby přestavuje strom funkcemi {\tt bbtree_collect} a {\tt bbtree_rebuild}
void bbtree_oprav(struct node *ptr) {
  struct node *parent=ptr->parent;
  bbtree_update_vrcholu(ptr);
  if (ptr->left_c/2 > ptr->right_c || ptr->right_c/2 > ptr->left_c) {//přestavba stromu?
    struct node *tmp;
    tmp=bbtree_rebuild(bbtree_collect(ptr),&tmp);

    if (parent && parent->value > ptr->value) parent->left=tmp;
    else if (parent && parent->value < ptr->value) parent->right=tmp;
    else root=tmp;
    tmp->parent=parent;
  }
  if (parent) bbtree_oprav(ptr->parent); //propagace výš
}

int main(void) {
  int i;

  printf("Zadejte N a K:");
  scanf("%d %d",&N,&K);

  for (i=0;i<N;i++) {
    int v=i%K;

    if (i >= K) bbtree_remove(hodnoty[v]); //budeme mazat?
    scanf("%d",hodnoty+v);
    bbtree_insert(hodnoty[v]);

    if (i) printf("Aktuální nejmenší rozdíl je %d.\n",root->delta);
  }
  return 0;
}