fromList :: Ord a => Int -> [a] -> Treap a
fromList seed xs = foldl insert (empty seed) xs


empty :: Int -> Treap a
empty seed = Treap (R.mkStdGen seed) Leaf


height :: Treap a -> Int
height = height' . extractBranch
    where
        height' Leaf = 0
        height' (Branch left  x y right) = 1 + max (height' left) (height' right)


buildTreeAndGetData :: [Int] -> R.StdGen -> (Int, Int)
buildTreeAndGetData arr rng = (h, c)
    where
        (seed, rng') = R.next rng
        tr = fromList seed arr
        h = height tr
        c = member tr $ (fst $ R.next rng) `mod` 1000


printData :: [Int] -> IO()
printData arr = do
    rng <- R.newStdGen
    let d@(h, c) = buildTreeAndGetData arr rng
    print d


runBenchmark :: Int -> IO()
runBenchmark nodeCount = do
    printData [1..nodeCount]


main = mapM_ runBenchmark [1000, 2000..10000]