type 'a queue = Node of 'a * int * 'a queue * 'a queue | Null
let empty = Null
let is_empty qu1 = qu1 = empty
exception Empty

let find_npl qu1 =
  match qu1 with
  | Node (_, b, _, _) -> b
  | Null -> (-1)

let rec join qu1 qu2 =
  match qu1, qu2 with
  | Null, a -> a
  | a, Null -> a
  | Node (val1, _, lq1, rq1), Node (val2, _, lq2, rq2) ->
    if val2 < val1 then join qu2 qu1 else
      let new_lq = join (qu2) (rq1) in
      let new_rq = lq1 in
      if find_npl new_lq < find_npl new_rq then (Node(val1, (find_npl new_lq) + 1, new_rq, new_lq))
      else (Node(val1, (find_npl new_rq) + 1, new_lq, new_rq))

let add el qu1 = join (Node(el, 0, empty, empty)) (qu1)

let delete_min qu1 =
  match qu1 with
  | Node (val1, npl1, lq1, rq1) -> (val1, join (lq1) (rq1))
  | Null -> raise Empty