import Control.Monad
import Data.Maybe
import qualified Data.ByteString.Char8 as BS --(ByteString, getLine, readInt, words)
import qualified  Data.ByteString as B
import Data.Array.Unboxed (UArray)
import Data.Array (Array, listArray, array, (!), (//), indices, elems, assocs) 

import Data.Bits (shift, shiftR, (.|.), (.&.)) --  bits `shift` 1
import Data.List (sort, sortOn)
import Data.Char --(toLower, toUpper, isUpper)
import Data.Ord -- Data.Ord.Down 
import Data.Array.ST  --(newListArray, runSTUArray, newArray, writeArray, readArray)
import Data.Array.IO 
import Control.Monad.ST (ST)
import Data.List.Extra (snoc)
import Data.Time (getCurrentTime, diffUTCTime)

import qualified Data.Sequence               as Seq
import qualified Data.Set                    as Set
import qualified Data.Vector.Unboxed         as V
import qualified Data.Vector.Unboxed.Mutable as VM
-- import Data.Time.LocalTime


-- example: putStrLn show 123 ++ "and" ~~ 456 ++ "or" ~~ 789
(~~) :: Show a => String -> a -> String
a ~~ b = a ++ show b

bslen = BS.length -- o(1)
bshd = BS.head -- o(1)
bstl = BS.tail -- o(1)
bslst = BS.last -- o(1)
bsini = BS.init -- o(1)
charToInt n = ord n - ord '0'
readi n = read n :: Int

bsToInt :: BS.ByteString -> Int
bsToInt = fst . fromJust . BS.readInt
getInt = bsToInt <$> BS.getLine

bsToInts :: BS.ByteString -> [Int]
bsToInts = map bsToInt . BS.words 
getInts = bsToInts <$> BS.getLine

getLines :: Int -> IO [BS.ByteString]
getLines n = replicateM n BS.getLine

getLinesToInts :: Int -> IO [Int]
getLinesToInts n = replicateM n $ bsToInt <$> BS.getLine

mapPutStrLn :: [String] -> IO()
mapPutStrLn = mapM_ putStrLn

--Data.List.sortOn [0..9] -> [9..0]
testSortDown = print $ sortOn Data.Ord.Down [0..9]


-----------------------------------------------------------------------
-----------------------------------------------------------------------
-- Data.Array      Immutable non-strict(lazy?) arrays
-- make array
ary1 :: Array Int String
ary1 = array (1,3) [(1, "contain1"), (2, "contain2"), (3, "contain3")]

ary2 :: Array Int Int
ary2 = listArray (1, 10^10) [1..10^10]

--(!) : read an element ... o(1)
ary1_3 = ary1 ! 3 -- (3,"contain3")

-- (//) : overwrite elements ... o(n)
-- actually, deep copy
ary1write :: Array Int String
ary1write = ary1 // [(1, "contain1_modified"), (3, "contain3_modified")]

-- bounds  ary1 -> (1,3)
-- indices ary1 -> [1,2,3]
-- elems   ary1 -> ["contain1", "contain2", "contain3"]



-----------------------------------------------------------------------
-----------------------------------------------------------------------
-- Mutable Arrays
-- Data.Array.ST (newListArray, newArray, writeArray, readArray, runSTUArray)
-- You can extract STUArray to UArray (Data.Array.Unboxed)

uary1 :: UArray Int Bool -- UArray is Immutable!
uary1 = runSTUArray $ stuaryInitVal

stuaryInitVal  :: ST s (STUArray s Int Bool) -- Mutable!
stuaryUndefVal :: ST s (STUArray s Int Bool)
stuaryFromList :: ST s (STUArray s Int Int)
stuaryInitVal  = newArray     (1, 9)  True
stuaryUndefVal = newArray_    (1, 9)
stuaryFromList = newListArray (1, 9) [0..]

-- readArray and writeArray ... o(1) 
-- readUary  = readArray uary1 1
-- writeUary = writeArray uary1 1 True
readStu = stuaryInitVal >>= (`readArray` 1)
writeStu = stuaryInitVal >>= (\x -> writeArray x 1 False)


-- Data.Array.IO (newListArray,..)
-- You CAN'T extract IOUArray 
iouaryInitVal  :: IO (IOUArray Int Int) -- Mutable!
iouaryUndefVal :: IO (IOUArray Int Int)
iouaryFromList :: IO (IOUArray Int Int)
iouaryInitVal  = newArray     (1, 9) 1 
iouaryUndefVal = newArray_    (1, 9)
iouaryFromList = newListArray (1, 9) [0..]

-- readArray and writeArray ... o(1) 
readIou = iouaryInitVal >>= (`readArray` 1)
writeIou = iouaryInitVal >>= (\x -> writeArray x 1 100)


newints :: Int -> Int -> Int -> IO(IOUArray Int Int)
newints start n = newArray (start, n)

rd :: IOUArray Int Int -> Int -> IO Int
rd = readArray

wt :: IOUArray Int Int -> Int -> Int -> IO()
wt = writeArray

--example: effect  (newArray (1, 3) 0)  3 (+100)   ->   array [(1,0), (2,0), (3,100)]
effect :: IOUArray Int Int -> Int -> (Int -> Int) -> IO()
effect ary i operator = (operator <$> readArray ary i) >>= writeArray ary i

-----------------------------------------------------------------------
-----------------------------------------------------------------------

-- Data.Set
setFromList    = Set.fromList [1,1,4,2,3,3,4,4]      -- -> set [1,2,3,4],       o(n*log n)
setFromAscList = Set.fromAscList [1,1,4,2,2,3,3,4,4] -- -> set [1,  4,  2,3,4], o(n)
setSize        = Set.size setFromList                -- -> 4,                   o(1)
setToList      = Set.toList setFromList              -- -> [1,2,3,4],           o(n)
-- toAscList, toDecList


main :: IO ()
main = do
    x1 <- getInt
    let t1 = length . takeWhile (< x1) $ iterate (\x -> truncate(fromIntegral x * 1.01)) 100 
    print $ t1 











Measured memory_bytes: 3776