type t = Empty | Node of t * (int * int) * t * (int * int) * int
exception Impossible
open Printf

let empty = Empty
let is_empty avl = avl = Empty

let numbers_between (a, b) = b - a + 1
let numbers_of x = match x with | Empty -> (0, 0) | Node (_, _, _, a, _) -> a
let min_of a = match a with | Empty -> min_int | Node (_, (b, c), _, _, _) -> b
let height_of x = match x with | Empty -> 0 | Node (_, _, _, _, a) -> a
let make_node l v r = Node (l, v, r,
  (let (ln, li) = numbers_of l in
  let (rn, ri) = numbers_of r in
    if numbers_between v = max_int then (0, 1)
    else if numbers_between v <= 0 then (0, 1)
    else if li = 2 || ri = 2 then (min_int, 2)
    else if li = 1 || ri = 1 then (ln + rn + numbers_between v, 1)
    else if min_int + ln + rn + numbers_between v = max_int then (0, 1)
    else if min_int + ln + rn + numbers_between v >= 0 then (min_int + ln + rn + numbers_between v, 1)
    else if min_int + ln + rn + numbers_between v = min_int then (min_int + ln + rn + numbers_between v, 2)
    else (ln + rn + numbers_between v, 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

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

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

let rec add_one x t =
match t with
| Node (l, k, r, els, h) ->
    let c = cmp x k in
    if c < 0 then
      let nl = add_one x l in
      bal nl k r
    else if c > 0 then
      let nr = add_one x r in
      bal l k nr
    else raise Impossible
| Empty -> make_node Empty x Empty

let rec join l v r =
  match (l, r) with
  | (Empty, _) -> add_one v r
  | (_, Empty) -> add_one v l
  | (Node(ll, lv, lr, el_l, lh), Node(rl, rv, rr, el_r, 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 merge sm gr =
    match sm with
    | Node (l, v, r, n, h) -> let nr = (merge r gr) in bal l v nr
    | Empty -> gr

let split_help x t =
  let clear = (Empty, false, Empty, x, x) in
    let rec loop x t (s, c, g, l_a, r_a) =
      match t with
      |  Empty -> (s, c, g, l_a, r_a)
      | Node (l, (a, b), r, _, _) ->
          let d = cmp (x, x) (a, b) in
          if d = -3 then
            let (ss, cc, gg, l_aa, r_aa) = loop x l clear
            in (merge s ss, false, merge g (merge gg r), l_aa, max (max r_a r_aa) b) else
          if d = 3 then
            let (ss, cc, gg, l_aa, r_aa) = loop x r clear
            in (merge s (merge l ss), false, merge gg g, min (min l_a l_aa) a, r_aa) else
          if d = -2 then
            let (ss, cc, gg, l_aa, r_aa) = loop x l clear
            in (merge s ss, cc || c, merge g (join gg (a, b) r), l_aa, r_aa) else
          if d = 2 then
            let (ss, cc, gg, l_aa, r_aa) = loop x r clear
            in (merge s (join l (a, b) ss), cc || c, merge gg g, l_aa, r_aa) else
          if d = -1 then
            (merge s l, true, merge r g, x, b) else
          if d = 1 then
            (merge s l, true, merge r g, a, x) else
          if d = 0 then
            (merge s l, true, merge r g, a, b) else raise Impossible
  in loop x t clear

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

let remove (x, y) t =
  let (s, _, _, a, _) = split_help x t in
  let (_, _, g, _, b) = split_help y t in
  let s = if x - a > 0 then add_one (a, x - 1) s else s 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
  let g = (if r_a > x then (add_one (x + 1, r_a) g) else g) in
  let s = (if l_a < x then (add_one (l_a, x - 1) s) else s) in
  (s, c, 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 s =
  match t with
  | Empty -> (0, 0)
  | Node (l, (a, b), r, (n, i), h) ->
    if x > b then
      (let (ln, li) = numbers_of l in
      let (b_n, b_i) = below_help x r 0 in
      if b_i > 0 then (max_int, 1)
      else if li > 0 then (max_int, 1)
      else if min_int + b_n + ln + b - a + 1 >= 0 then (max_int, 1)
      else if min_int + b_n + ln + b - a + 1 = min_int then (max_int, 2)
      else (b_n + ln + b - a + 1, 0))
    else if x >= a then
      (let (ln, li) = numbers_of l in
      if li > 0 then (max_int, 1)
      else if min_int + ln + x - a + 1 >= 0 then (max_int, 1)
      else if min_int + ln + x - a + 1 = min_int then (max_int, 2)
      else (ln + x - a + 1, 0))
    else
      (let (aa, ii) = below_help x l s in
      if ii > 0 then (max_int, 1)
      else if min_int + aa >= 0 then (max_int, 1) else (aa, 0))

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