module IntMap = Map.Make (struct
  type t = int
  let compare = compare
end)

let add a s =
  IntMap.add a (1 + try IntMap.find a s with Not_found -> 0) s

let remove a s =
  match IntMap.find a s with
  | exception Not_found -> s
  | 1 -> IntMap.remove a s
  | n -> IntMap.add a (n - 1) s

let _ =
  Array.fold_left (fun (odd, acc, (q, q')) ->
    let (m, _) = IntMap.max_binding q in
    function
    | None ->
        Printf.printf "%d %d\n" m acc;
        (odd, acc, (q, q'))
    | Some (a, b) ->
        not odd,
        ( acc + b +
          if odd then
            abs (m - a)
          else
            let (m', _) = IntMap.min_binding q' in
            if a <= m then
              m - a
            else if m' <= a then
              a - m'
            else 0 ),
        if a < m then
          let q = add a q in
          if not odd
          then (q, q')
          else (remove (fst (IntMap.max_binding q)) q, add (fst (IntMap.max_binding q)) q')
        else
          let q' = add a q' in
          if odd
          then (q, q')
          else (add (fst (IntMap.min_binding q')) q), remove (fst (IntMap.min_binding q')) q')
  (false, 0, (IntMap.singleton min_int 1, IntMap.singleton max_int 1)) @@
  Scanf.scanf "%d " @@ fun q ->
    Array.init q @@ fun _ ->
      Scanf.scanf "%d " @@ function
        | 2 -> None
        | 1 -> Scanf.scanf "%d %d " @@ fun a b -> Some (a, b)
