data Q a = Empty
           | Q {qF::[a], qM::Q [a], qLFM::Int, qR::[a], qLR::Int}
           deriving (Show)

qSnoc::Q a->a->Q a
qSnoc Empty e = Q {qF = [e], qM = Empty, qLFM=1, qR=[], qLR = 0}
qSnoc q e = qBalance q{qR = e : qR q, qLR = qLR q + 1}

qHead::Q a -> a
qHead q = head (qF q)

qTail::Q a->Q a
qTail q = qBalance q{qF = tail (qF q), qLFM = qLFM q - 1}

qBalance::Q a->Q a
qBalance q = qBalF (qBalR q)

qBalR::Q a->Q a
qBalR q
  | qLR q <= qLFM q = q
  | otherwise = q{qM = qSnoc (qM q) (reverse $ qR q),
                  qLFM = qLFM q + qLR q,
                  qR = [], qLR = 0}

qBalF::Q a->Q a
qBalF q
  | not (null $ qF q) = q
  | Empty <- qM q = Empty
  | otherwise = q{qF = qHead m, qM = qTail m}
  where
    m = qM q