type t = Empty | Node of t * (int * int) * t * (int * int) * int
(* typ t = Empty lub Node (lewe drzewo; przedzial (a, b) w danym wierzcholku; prawe_drzewo; (c, d), gdzie jezeli d = 0, c oznacza liczbę wierzcholkow, w innym przypadku c = max_int; wysokosc_drzewa) *)
exception Impossible (* wyjatek opisujacy przypadki, ktore nigdy nie zostana wywolane *)

let empty = Empty
let is_empty avl = avl = Empty

let numbers_of x =
  match x with
  | Empty -> (0, 0)
  | Node (_, _, _, a, _) -> a

let height_of x =
  match x with
  | Empty -> 0
  | Node (_, _, _, _, a) -> a

(* tworzymy drzewo ktorego lewy syn, prawy syn i wartosc w wierzcholku sa dane - jezeli liczba elementow <= 0 lub rowna max_int tzn, ze jest ich >= max_int *)
let make_node l (a, b) r = Node (l, (a, b), r, (
  let (ln, li) = numbers_of l in
  let (rn, ri) = numbers_of r in
    if b - a + 1 <= 0 || li > 0 || ri > 0 then (0, 1)
    else if ln + rn + b - a + 1 <= 0 then (0, 1)
    else if ln + rn + b - a + 1 = max_int then (0, 1)
    else (ln + rn + b - a + 1, 0)),
  (max (height_of l) (height_of r)) + 1)

let rec fold f avl acc =
  match avl with
  | Empty -> acc
  | Node (l, (a, b), r, _, _) -> fold f r (f (a, b) (fold f l acc))

let rec iter f avl =
  match avl with
  | Empty -> ()
  | Node (l, v, r, _, _) -> iter f l; f v; iter f r

(* operacja tworzenia drzewa - z maksymalnie jednym "balansowaniem" do wykonania *)
let bal l k r =
  let hl = height_of l in
  let hr = height_of r in
  if hl > hr + 2 then
    match l with
    | Node (ll, lk, lr, _, _) ->
        if height_of ll >= height_of lr then make_node ll lk (make_node lr k r) else
          (match lr with
          | Node (lrl, lrk, lrr, _, _) ->
              make_node (make_node ll lk lrl) lrk (make_node lrr k r)
          | Empty -> assert false)
    | Empty -> assert false
  else if hr > hl + 2 then
    match r with
    | Node (rl, rk, rr, _, _) ->
        if height_of rr >= height_of rl then make_node (make_node l k rl) rk rr else
          (match rl with
          | Node (rll, rlk, rlr, _, _) ->
              make_node (make_node l k rll) rlk (make_node rlr rk rr)
          | Empty -> assert false)
    | Empty -> assert false
  else make_node l k r

(* rozpatrujemy rozne przypadki nachodzenia na siebie przedzialow
funkcja jest wykorzystywana tylko w add_one oraz w split_help dla (a, b) = (a, a),
czyli dla split mozemy porownywac tylko b wzgledem (c, d),
a dla add_one podobnie, bo zalozenie jest takie, ze przedzialy w add_one na siebie nie nachodza *)
let cmp (a, b) (c, d) =
  if b = c - 1 && c <> min_int then -3 else
  if b < c then -2 else
  if b = c then -1 else
  if b > c && b < d then 0 else
  if b = d then 1 else
  if b = d + 1 && d <> max_int then 3 else
  if b > d then 2 else 4

(* warunek poczatkowy - przedzial x ktory chcemy dodac do drzewa nie moze polaczyc sie z zadnym innym w drzewie,
tzn nie ma przedzialow (a, x-1) oraz (x+1, b) (z uwzglednieniem min_int, max_int) lub nachodzacych na x *)
let rec add_one x t =
match t with
| Node (l, k, r, _, _) ->
    let c = cmp x k in
    if c < 0 then bal (add_one x l) k r
    else if c > 0 then bal l k (add_one x r)
    else raise Impossible (* zalozenie add_one jest takie, ze przedzialy na siebie nie nachodza, zatem c nie bedzie rowne 0 dla wywolan cmp w add_one *)
| Empty -> make_node Empty x Empty

(* laczymy 2 drzewa z ustalona srodkowa wartoscia; warunek poczatkowy - drzewa l i r sa poprawne oraz (a, b) jest
wieksze niz dowolna wartosc z l i mniejsze niz dowolna wartosc z r *)
let rec join l v r =
  match (l, r) with
  | Empty, _ -> add_one v r
  | _, Empty -> add_one v l
  | Node (ll, lv, lr, _, lh), Node (rl, rv, rr, _, rh) ->
      if lh > rh + 2 then bal ll lv (join lr v r) else
      if rh > lh + 2 then bal (join l v rl) rv rr else
      make_node l v r

let rec min_elt t =
  match t with
  | Node (Empty, v, _, _, _) -> v
  | Node (l, _, _, _, _) -> min_elt l
  | Empty -> raise Impossible (* funkcja nigdy nie jest wywolywana dla s = Empty (patrz merge nizej) *)

let rec remove_min_elt t =
  match t with
  | Node (Empty, _, r, _, _) -> r
  | Node (l, v, r, _, _) -> bal (remove_min_elt l) v r
  | Empty -> raise Impossible (* funkcja nigdy nie jest wywolywana dla s = Empty (patrz merge nizej) *)

let merge t1 t2 =
  match t1, t2 with
  | Empty, _ -> t2
  | _, Empty -> t1
  | _ ->
      let v = min_elt t2 in
      join t1 v (remove_min_elt t2)

(* w zaleznosci od cmp (x, x) (a, b) dzielimy drzewo - funkcja zwraca (drzewo mniejszych wartosci, czy x znajduje sie w drzewie,
drzewo wiekszych wartosci, ewentualny dodatek z lewej, ewentualny dodatek z prawej), gdzie "dodatki" to adnotacja, dokad rozszerzy
sie przedzial, gdy laczy sie on z x *)
let split_help x t =
  let rec loop x t (ld, rd)=
    match t with
    | Empty -> (Empty, false, Empty, x, x)
    | Node (l, (a, b), r, _, _) ->
        let d = cmp (x, x) (a, b) in
        if d = -2 then
          let (nl, cc, nr, n_l, n_r) = loop x l (x, x)
          in (nl, cc, join nr (a, b) r, min ld n_l, max rd n_r) else

        if d = 2 then
          let (nl, cc, nr, n_l, n_r) = loop x r (x, x)
          in (join l (a, b) nl , cc, nr, min ld n_l, max rd n_r) else

        if d = 0 then (l, true, r, a, b) else

        if d = -1 then (l, true, r, ld, b) else

        if d = 1 then (l, true, r, a, rd) else

        if d = -3 then
          let (nl, cc, nr, n_l, n_r) = loop x l (x, x)
          in (nl, false, merge nr r, min ld n_l, b) else

        if d = 3 then
          let (nl, cc, nr, n_l, n_r) = loop x r (x, x)
          in (merge l nl, false, nr, a, max rd n_r)

        else raise Impossible (* cmp rozpatruje wszystkie przypadki dla (x, x) (a, b), zatem nie bedzie innego przypadku niz liczby calkowite z przedzialu <-3, 3> *)
  in loop x t (x, x)

let add (x, y) t =
  let (s, _, _, a, _) = split_help x t in
  let (_, _, g, _, b) = split_help y t in
  join s (a, b) g

let remove (x, y) t =
  let (s, _, _, a, _) = split_help x t in
  let (_, _, g, _, b) = split_help y t in
  let g = if x - a > 0 then add_one (a, x - 1) g else g in
  let g = if b - y > 0 then add_one (y + 1, b) g else g in
  merge s g

let split x t =
  let (s, c, g, l_a, r_a) = split_help x t in
  ((if l_a < x then (add_one (l_a, x - 1) s) else s),
  c,
  (if r_a > x then (add_one (x + 1, r_a) g) else g))

let elements x =
  let rec loop acc x =
    match x with
    | Empty -> acc
    | Node(l, k, r, _, _) -> loop (k :: (loop acc r)) l in
    loop [] x

let rec mem x t =
  match t with
  | Empty -> false
  | Node (l, (a, b), r, _, _) ->
    if x >= a && x <= b then true
    else if x < a then mem x l else mem x r

let rec below_help x t =
  match t with
  | Empty -> (0, 0)
  | Node (l, (a, b), r, _, _) ->
    let (ln, li) = numbers_of l in
    if x > b then
      let (b_n, b_i) = below_help x r in
      if b_i > 0 || li > 0 then (max_int, 1)
      else if b_n + ln + b - a + 1 <= 0 then (max_int, 1)
      else (b_n + ln + b - a + 1, 0)
    else if x >= a then
      if li > 0 then (max_int, 1)
      else if ln + x - a + 1 <= 0 then (max_int, 1)
      else (ln + x - a + 1, 0)
    else below_help x l

let below x t =
  let (ans, _) = below_help x t in ans