import System (getArgs, getProgName)
import System.Random.Mersenne (MTRandom, randomIO)
import Data.IntMap (IntMap, lookup, insert, empty, size, keys, (!))
import Data.Word (Word8)
import Data.Array.Unboxed (UArray, listArray, bounds, elems)
import Data.Maybe (isJust, fromJust)
import Data.Foldable (foldrM, foldl')

-- data types

type Data = IntMap (UArray Int Word8)

-- generate a random number in a given range, using System.Random.Mersenne
randomNumberMersenne :: (Integral a, MTRandom a) => (a,a) -> IO a
randomNumberMersenne (i1,i2) = do
			r <- randomIO
			return (r `mod` (i2 - i1) + i1)

-- add one pair to the map
addOne :: Int -> Data -> IO Data
addOne _ m = do
		id <- randomNumberMersenne (1,480109) :: IO Int
		val <- randomNumberMersenne (1,5) :: IO Word8
		let mUa = Data.IntMap.lookup id m
		    vs  = if (isJust mUa) then (elems . fromJust) mUa else [] :: [Word8]
		    s   = if (isJust mUa) then (snd . bounds . fromJust) mUa else 0 :: Int
		    ua' = listArray (1,s+1) $ val:vs
		ua' `seq` return $ insert id ua' m

-- strict sum
sum' = foldl' (+) 0

-- MAIN
main = do
	args <- getArgs
	progName <- getProgName
	let n = read (args !! 0) :: Int
	putStrLn $ "pushing " ++ (show n) ++ " pairs into an IntMap..."
	idValMap <- foldrM addOne empty [1..n]
	putStrLn . show $ size idValMap
	putStrLn . show $ sum' (map (\k -> length . elems $ idValMap ! k) $ keys idValMap)